## 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

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

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

Loading comments...