Flood Fill
Understanding the Problem
We are given a 2D grid of pixel values and a starting pixel at position (sr, sc). Our job is to change the color of the starting pixel and all connected pixels that share the same original color. "Connected" means reachable through a chain of 4-directional (up, down, left, right) neighbors that all have the same original color.
This is the "paint bucket" tool in any image editor. Click somewhere, and every pixel of the same color that is connected to your click gets recolored. Two pixels of the same color that are separated by a differently colored pixel are not connected, even though they share the same value, so only one of those regions changes.
Finding all connected pixels is a graph traversal. Treat each pixel as a node and each 4-directional adjacency as an edge. Starting from (sr, sc), we visit every reachable node whose value matches the original color and repaint it. Both DFS and BFS do this.
Key Constraints:
1 <= m, n <= 50-> The grid holds at most 2,500 cells. An O(m * n) traversal that visits every cell is fast enough, so the work is in getting correctness right.0 <= sr < m, 0 <= sc < n-> The starting pixel is always inside the grid, so readingimage[sr][sc]is safe without a bounds check.
Approach 1: DFS (Recursive)
Intuition
Flood fill maps directly onto recursion. Start at the given pixel, repaint it, then check each of its 4 neighbors. If a neighbor has the same original color, flood fill it the same way. If not, stop.
This is a depth-first search on a 2D grid. The graph is implicit: nodes are pixels, and edges connect each pixel to its 4 neighbors (up, down, left, right). We repaint every node we reach.
The one hazard is an infinite loop. Repainting a pixel from originalColor to color makes it stop matching originalColor, so the recursion will not return to it. That breaks down when color == originalColor: repainting changes nothing, the pixel keeps matching, and the recursion revisits it forever. Guard against it upfront. If the new color equals the original color, return the image unchanged, since there is nothing to repaint.
Algorithm
- Record the original color at position
(sr, sc). - If the original color equals the new color, return the image as-is (nothing to change).
- Call a recursive helper starting at
(sr, sc). - In the helper:
- Paint the current pixel with the new color.
- For each of the 4 neighbors (up, down, left, right):
- If the neighbor is within bounds and has the original color, recurse on it.
- Return the modified image.
Example Walkthrough
Code
- Time Complexity: O(m * n). In the worst case, every pixel has the same color and is connected to the starting pixel. We visit each pixel exactly once, doing O(1) work per pixel.
- Space Complexity: O(m * n). The recursion stack can grow as deep as the number of pixels in the worst case, when DFS follows a long winding path through all cells.
The recursive DFS visits each pixel once, which is optimal in time, but a long connected region pushes one stack frame per pixel and can overflow the call stack. The next approach runs the same traversal with an explicit queue, moving that memory off the call stack.
Approach 2: BFS (Iterative)
Intuition
BFS runs the same traversal as DFS using an explicit queue instead of recursion. Start at (sr, sc), repaint it, then visit all 4-connected neighbors that still hold the original color. BFS expands outward in rings from the starting pixel while DFS goes deep along one path first, but both visit the same set of pixels and produce the same result.
The reason to prefer BFS is practical. The queue lives on the heap, so a large connected region grows the queue rather than the call stack, avoiding the stack-overflow risk of deep recursion. Time and space complexity are unchanged.
Neither approach keeps a separate visited set, yet neither revisits a pixel. Repainting is what marks a pixel as visited: once a pixel changes from originalColor to color, the check image[row][col] == originalColor fails for it, so it is never enqueued or recursed into again. Because each repainted pixel is added to the frontier exactly once, the traversal terminates after touching every connected same-color pixel.
This is why the originalColor == color guard is required. When the two colors are equal, repainting leaves the value unchanged, the match check never starts failing, and there is no way to tell visited pixels from unvisited ones.
Algorithm
- Record the original color at position
(sr, sc). - If the original color equals the new color, return the image as-is.
- Create a queue and add
(sr, sc)to it. - Paint
image[sr][sc]with the new color. - While the queue is not empty:
- Dequeue a pixel
(row, col). - For each of the 4 neighbors:
- If the neighbor is within bounds and has the original color, paint it with the new color and enqueue it.
- Return the modified image.
Example Walkthrough
Code
- Time Complexity: O(m * n). Same as DFS. Every pixel is enqueued and dequeued at most once.
- Space Complexity: O(m n). The queue can hold at most O(m n) pixels in the worst case, when all pixels are connected and have the same color.