Level Order

 source code

Flood fill

Given the row and column of a pixel in an m x n image, change all neighboring pixels of the same color to a new color. Neighboring pixels are located above, below, to the left, or to the right of a pixel.

Input:   image = 1 1 1 1
                 0 1 1 1
                 0 0 1 1
         row = 0
         col = 0
         color = 2
Output:  2 2 2 2
         0 2 2 2
         0 0 2 2
Solution Time Space
Breadth-first search O(mn) O(mn)
Depth-first search O(mn) O(mn)

Solution 1: Breadth-first search

def flood_fill(image, row, col, color)
  m, n = image.length, image[0].length
  old_color = image[row][col]
  return image if old_color == color
  queue = []
  queue << [row, col]
  while queue.length > 0
    row, col = queue.shift
    next if image[row][col] != old_color
    image[row][col] = color
    queue << [row-1, col] if row-1 >= 0
    queue << [row+1, col] if row+1 <= m-1
    queue << [row, col-1] if col-1 >= 0
    queue << [row, col+1] if col+1 <= n-1
  end
  image
end
Time O(mn) Checking up to every pixel in the image
Space O(mn) Queue size

Solution 2: Depth-first search

def flood_fill(image, row, col, color)
  m, n = image.length, image[0].length
  old_color = image[row][col]
  return image if old_color == color
  dfs = lambda do |row, col|
    return if row < 0 || row >= m
    return if col < 0 || col >= n
    return if image[row][col] != old_color
    image[row][col] = color
    dfs.call(row-1, col)
    dfs.call(row+1, col)
    dfs.call(row, col-1)
    dfs.call(row, col+1)
  end
  dfs.call(row, col)
  image
end
Time O(mn) Checking up to every pixel in the image
Space O(mn) Stack depth

Resources