Flood Fill
Flood Fill is LeetCode 733 (Easy). An image is stored as an m × n grid of integers, where each number is the colour of one pixel. You are also given a starting pixel (sr, sc) and a new color.
Repaint the region that contains the starting pixel, exactly like the paint-bucket tool in an image editor:
- The region starts with
image[sr][sc]; call its colour the original colour. - A pixel joins the region if it has the original colour and touches a region pixel up, down, left or right. Diagonal contact does not count.
- Every pixel in the region becomes
color. Every other pixel keeps its value.
Return the modified image. The grid is at most 50 × 50, so a single visit per pixel is all the work there is.
- m == image.length
- n == image[i].length
- 1 <= m, n <= 50
- 0 <= image[i][j], color < 2¹⁶
- 0 <= sr < m
- 0 <= sc < n
Intuition
The pixels with the original colour that touch each other 4-directionally form a connected component of a grid graph: every pixel is a vertex and every up/down/left/right pair of equal pixels is an edge. Flood fill is just "visit every vertex in the component of (sr, sc)", which any graph traversal does.
The neat part is that the repainting is the visited marker. Once a pixel has the new colour it no longer equals the original colour, so the neighbour check rejects it and it is never visited twice. No separate visited array is needed, as long as the new colour really differs from the old one.
The flood fill LeetCode problem is the template for a whole family. Grid questions that ask you to spread from one cell to every connected cell with the same value are the flood fill algorithm: Number of Islands counts components with it, Max Area of Island measures them, Surrounded Regions and Rotting Oranges spread a mark through them. Whenever a problem says "4-directionally connected", think flood fill.
Approach
Before reading on: what happens to your code if color == image[sr][sc]? Trace it on a 1 × 2 grid of the same colour. Then write the fill without a visited set.
Two ways to solve it
Paint the start, push it, then pop pixels and paint and push their matching neighbours until the stack is empty.
- Depth: no recursion limit to hit.
- Pushes: each pixel at most once.
- Marker: paint at push time, no visited set.
Safe for any region shape.
A helper fill(r, c) returns on an out-of-bounds or wrong-colour pixel, otherwise paints it and calls itself on the four neighbours.
- Code: the shortest version.
- Depth: one frame per pixel on a long path.
- Risk: Python's default limit is 1,000.
Fine where the stack is deep enough.
Both paint the same pixels with the same work, but the explicit stack cannot overflow the call stack on a long, snaking region. The steps, code and live demo below follow the stack version; the recursive code comes after the demo.
Remember the original colour
Read old = image[sr][sc] before changing anything. If old == color, return the image at once: the answer is the image itself, and the paint-as-visited trick would never terminate.
Paint the start and put it on a stack
Set image[sr][sc] = color and push (sr, sc). Painting at push time, not pop time, is what guarantees each pixel enters the stack only once.
Pop a pixel and check its four neighbours
For each of (r+1, c), (r-1, c), (r, c+1), (r, c-1):
- outside the grid: skip;
- colour is not
old(a different colour, or already painted): skip; - otherwise: paint it and push it.
Stop when the stack is empty
Return image. A pixel is painted only when it has the original colour and touches a painted pixel, so nothing outside the region changes, and the search follows every chain of equal neighbours from the start, so no region pixel is missed.
Flood Fill solution in Python | C++ | Java
Recursive DFS flood fill
Each call checks one pixel. If it is inside the grid and still has the original colour, it is painted and the call spreads to its four neighbours; painted pixels stop the recursion.
Common pitfalls
No early return when the colour is unchanged
old = image[sr][sc] image[sr][sc] = color stack = [(sr, sc)]
old = image[sr][sc]
if old == color:
return imagePainting is the only visited marker. With color == old a painted pixel still equals old, so neighbours push each other back and forth forever: an infinite loop iteratively, a stack overflow recursively.
Reading the colour after the first paint
image[sr][sc] = color old = image[sr][sc]
old = image[sr][sc] image[sr][sc] = color
old now equals color, so no neighbour matches and only the start pixel changes. Save the original colour before touching the grid.
Deep recursion in Python
def fill(r, c):
...
fill(r + 1, c)stack = [(sr, sc)]
while stack:
r, c = stack.pop()A snake-shaped region in a 50 × 50 grid is a path of up to 2,500 pixels, and a recursive flood fill Python solution goes one frame deeper per pixel. That passes CPython's default limit of 1,000, so it crashes anywhere the limit is not raised. An explicit stack has no such limit.
Checking the colour before the bounds
if image[nr][nc] == old and 0 <= nr < rows and 0 <= nc < cols:
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
The colour read runs first, so nr == rows raises an index error. Worse, in Python nr == -1 silently reads the last row and can paint pixels on the far side of the image. Test the bounds first and let and short-circuit.
Complexity
Flood Fill FAQ
What is the flood fill algorithm?
Flood fill starts at one cell and spreads to every cell connected to it that has the same value, changing each one as it goes. It is a depth-first or breadth-first search on the grid, where neighbouring cells with equal values are joined by edges. It powers the paint-bucket tool, region selection in image editors and the island-counting family of interview problems.
Should flood fill use DFS or BFS?
Either. Both visit exactly the region and cost O(m · n). Swap the stack for a queue (deque.popleft()) and the code above becomes BFS, which fills in rings around the start; DFS snakes along one direction first. The final image is identical.