Flood Fill

Leetcode link: https://leetcode.com/problems/flood-fill/

Question#

Flood fill is a classic question. If you have used software like MS Paint or Photoshop, the paint bucket which cover all surrounding same-colored pixels with the new color of the paint bucket uses a flood fill algorithm.

Method 1 - With Queues#

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
def get_matching_neighbors(x, y, val):
max_col = len(image[0])
max_row = len(image)
neighbors = []
# check top
if(x - 1 >= 0):
if(image[x-1][y] == val):
neighbors.append([x-1, y])
# check right
if(y + 1 < max_col):
if(image[x][y+1] == val):
neighbors.append([x,y+1])
# check bottom
if(x + 1 < max_row):
if(image[x+1][y] == val):
neighbors.append([x+1,y])
# check left
if(y - 1 >= 0):
if(image[x][y-1] == val):
neighbors.append([x,y-1])
return neighbors
# check if new value is same as before
if(image[sr][sc] == newColor):
return image
queue = deque()
queue.append([sr,sc])
original_pixel = image[sr][sc]
while(len(queue) > 0):
curr_cor = queue.popleft()
neighbors = get_matching_neighbors(curr_cor[0], curr_cor[1], original_pixel)
queue += neighbors
image[curr_cor[0]][curr_cor[1]] = newColor
return image
  • Time complexity: O(n) where n is the number of pixels in image since we are touching all pixels
  • Space complexity: O(n) due to use of queue

Method 2 - Depth First Search#

We can use a recursive depth first search to perform the flood fill.

def floodFill(self, image, sr, sc, newColor):
R, C = len(image), len(image[0])
color = image[sr][sc]
if color == newColor: return image
def dfs(r, c):
if image[r][c] == color:
image[r][c] = newColor
if r >= 1: dfs(r-1, c)
if r+1 < R: dfs(r+1, c)
if c >= 1: dfs(r, c-1)
if c+1 < C: dfs(r, c+1)
dfs(sr, sc)
return image

We recursively repeat the dfs on all neighbours of the initial starting pixel.

  • Time complexity: O(n) where n is the number of pixels in image
  • Space complexity: O(n) due to recursive call stack