Depth-First Search
Flood Fill
DESCRIPTION (inspired by 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.
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).
Explanation
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
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
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
Complexity Analysis
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(m * n) In the worst case, every pixel in the grid has the same color as the starting pixel, so the DFS visits all m * n cells exactly once.
Space Complexity: O(m * n) In the worst case, the DFS recursion stack can grow up to m * n deep when all pixels share the same color and the recursion path snakes through the entire grid.
Mark as read
Unlock Premium Coding Content
On This Page
Your account is free and you can post anonymously if you choose.