DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Flood Fill

easyGraphs

Problem statement

You are given a grid of integers image, where each value is a pixel's colour, a starting cell (sr, sc), and a new colour color. Repaint the region that contains the starting cell: the starting cell and every cell reachable from it by moving up, down, left or right through cells of the same original colour as the start. Diagonal neighbours do not count.

Return the grid after repainting. If the start already has the new colour, nothing changes.

Examples

Example 1

Input: image = [[2, 2, 0], [2, 0, 0], [2, 2, 1]], sr = 0, sc = 0, color = 5

Output: [[5, 5, 0], [5, 0, 0], [5, 5, 1]]

Explanation: All the 2s are connected to the top-left corner, so they all become 5. The 0s and the 1 are untouched.

Example 2

Input: image = [[3, 3], [3, 3]], sr = 1, sc = 1, color = 3

Output: [[3, 3], [3, 3]]

Explanation: The new colour equals the old one, so the grid is returned unchanged.

Hints

Approach

Run a breadth-first search from the start cell and paint cells as they are discovered.

  1. Let old be the start cell's colour. If it equals color, return the grid.
  2. Paint the start cell and put it in a queue.
  3. Pop a cell. For each of its four neighbours that is inside the grid and still has colour old, paint it and push it.
  4. Stop when the queue is empty.

Painting a cell when it is pushed, not when it is popped, doubles as the visited mark: a painted cell no longer has colour old, so it is never pushed twice. That is also why the early return in step 1 is required; without it, painting would not change anything and the search would loop forever. A recursive DFS works the same way but can hit the recursion limit on a large region.

ComplexityTime O(m · n)Space O(m · n) for the queue in the worst case
Python
from collections import deque
class Solution:
def floodFill(self, image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
old = image[sr][sc]
if old == color: # otherwise painting would never mark cells as done
return image
rows, cols = len(image), len(image[0])
image[sr][sc] = color
queue = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
image[nr][nc] = color # paint on push: acts as the visited mark
queue.append((nr, nc))
return image

Follow-up questions

  • Count how many separate regions of each colour the image contains.
  • Allow diagonal moves as well. What changes?

Frequently asked questions

Painting a cell is what marks it as visited. If the colours are equal, painting changes nothing, so every cell keeps looking unvisited and the search revisits it forever. Return early in that case.

Both visit each cell once and give the same answer. Recursive DFS is shorter, but a region of a million cells can exceed the default recursion limit. BFS with a queue, or DFS with an explicit stack, avoids that.

It is the smallest graph-search problem, and grid search is the base of the harder questions: counting islands, spreading failures across a rack layout, or finding every host reachable from a starting point. Interviewers use it to check that you mark visited cells correctly and handle the grid edges.