An image is a grid of integers image[i][j] (pixel colours). Starting from pixel (sr, sc), perform a flood fill: change the starting pixel and every pixel connected to it horizontally or vertically through pixels of the same original colour to color. Return the modified image.
- 1 <= m, n <= 50
- 0 <= image[i][j], color < 2^16
- 0 <= sr < m, 0 <= sc < n
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Flood fill is the paint bucket tool. From the start pixel we spread to the four neighbours that still have the original colour, recolour them, and keep spreading. Recolouring doubles as the visited mark, because a recoloured pixel no longer matches the original colour. The only trap is when the new colour equals the old one: nothing would change, and without a check the search would revisit cells forever.
Algorithm
- Let
old = image[sr][sc]. Ifold == color, return the image unchanged. - Recolour the start pixel and push it on a stack.
- Pop a pixel and look at its 4 neighbours.
- For each neighbour inside the grid with colour
old, recolour it and push it. - When the stack is empty, return the image.
O(m * n)Space: O(m * n) for the stack in the worst caseold == color early return is exactly what interviewers watch for. Without it, recursive DFS hits infinite recursion on inputs like example 2.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: return image # nothing to change m, n = len(image), len(image[0]) image[sr][sc] = color stack = [(sr, sc)] while stack: r, c = stack.pop() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old: image[nr][nc] = color # recolouring also marks it visited stack.append((nr, nc)) return image