< Back




733. Flood Fill

We're given an m * n matrix of integers representing an image, a starting cell, and a new color.
We're asked to change the starting cell and all the cells connected to in 4 directions to the same
color. We're asked to recursively do this for all the cells that have also changed to the new color.
We only change cells that are the same color as the starting cell.

Using BFS, we maintain a seen set to avoid revisiting already seen cells, and we define an is_valid
helper method to detect if a cell reference is in bounds and if its color is the same as the starting
cell. We then iterate over the neighbors of the starting cell, and if they are valid, we add them to
the queue, mark them as seen, and change their color to the new color.

Eventually we visit all the cells that should be changed to the new color, and we return the updated
image.

The solution is as follows:


  class Solution:
      def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
          directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
          m, n, start_color = len(image), len(image[0]), image[sr][sc]

          def is_valid(x: int, y: int) -> bool:
              return -1 < x < m and -1 < y < n and image[x][y] == start_color

          queue, seen = [(sr, sc)], [0 for i in range(m * n)]
          seen[sr * n + sc] = 1

          while queue:
              curr_queue, queue = queue, []

              for x, y in curr_queue:
                  image[x][y] = color

                  for dx, dy in directions:
                      nx, ny = x + dx, y + dy

                      if is_valid(nx, ny) and not seen[nx * n + ny]:
                          seen[nx * n + ny] = 1
                          queue.append((nx, ny))

          return image


_ Time Complexity:

  O(m * n) - We create a seen array of size m * n, and in the worst case we visit all the cells.

_ Space Complexity:

  O(m * n) - We create a seen array of size m * n.