Back to Main
Learn DSA
Two Pointers
Sliding Window
Intervals
Stack
Linked List
Binary Search
Heap
Depth-First Search
Breadth-First Search
Backtracking
Graphs
Dynamic Programming
Greedy Algorithms
Trie
Prefix Sum
Matrices
Get Premium
Flood Fill
DESCRIPTION (credit Leetcode.com)
Given a m x n integer grid image and integers sr, sc, and newColor, write a function to perform a flood fill on the image starting from the pixel image[sr][sc].
In a 'flood fill', start by changing the color of image[sr][sc] to newColor. Then, change the color of all pixels connected to image[sr][sc] from either the top, bottom, left or right that have the same color as image[sr][sc], along with all the connected pixels of those pixels, and so on.
EXAMPLES
Input: image = [[1,0,1],[1,0,0],[0,0,1]], sr = 1, sc = 1, color = 2
Output: [[1,2,1],[1,2,2],[2,2,1]]
The zeroes connected to the starting pixel (1, 1) are colored with the new color (2).
Run your code to see results here
Explanation
This solution uses depth-first search to traverse the grid and perform the flood fill by defining a recursive function dfs that takes in the current row and column of the pixel being explored. Each call to dfs will either change the color of the pixel if the pixel is the same color as the starting pixel, and then recursively call dfs on its connected pixels. If the pixel is not the same color as the starting pixel, the function will return without doing anything.
The algorithm starts at the given starting pixel and uses depth-first search to explore all pixels connected 4-directionally to it. At each pixel, it first checks to see if the pixel is the same color as the starting pixel. If it is, it changes the color of the pixel and continues to explore the connected pixels.
def flood_fill(image, sr, sc, color):rows, cols = len(image), len(image[0])original_color = image[sr][sc]if original_color == color:return imagedef dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)returndfs(sr, sc)return image
def dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)return
update color
0 / 2
1x
After changing that pixel's color, the algorithm will continue to explore the connected pixels of that pixel. Whenever it encounters a pixel that is not the same color as the starting pixel, it will return immediately and backtrack to the previous pixel on the call stack, which will then continue to explore its remaining connected pixels.
def flood_fill(image, sr, sc, color):rows, cols = len(image), len(image[0])original_color = image[sr][sc]if original_color == color:return imagedef dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)returndfs(sr, sc)return image
def dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)return
def dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)return
def dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)return
recursive call
0 / 6
1x
The algorithm will continue to explore the connected pixels of the starting pixel until it has explored all connected pixels of the start pixel. The time complexity of this algorithm is O(n * m) where n is the number of rows and m is the number of columns in the grid.
Animated Solution
def flood_fill(image, sr, sc, color):rows, cols = len(image), len(image[0])original_color = image[sr][sc]if original_color == color:return imagedef dfs(r, c):if image[r][c] == original_color:image[r][c] = colorif r >= 1: dfs(r - 1, c)if r + 1 < rows: dfs(r + 1, c)if c >= 1: dfs(r, c - 1)if c + 1 < cols: dfs(r, c + 1)returndfs(sr, sc)return image
flood fill
0 / 39
1x
© 2025 Optick Labs Inc. All rights reserved.
Loading comments...