Flood Fill
Last Updated: March 28, 2026
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 essentially 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. The key word is "connected." Two pixels of the same color that are separated by a differently colored pixel are NOT connected, even though they share the same value.
The natural way to find all connected pixels is through graph traversal. We can treat each pixel as a node and each 4-directional adjacency as an edge. Starting from (sr, sc), we want to visit every reachable node whose value matches the original color, and repaint it. Both DFS and BFS do this perfectly.
Key Constraints:
1 <= m, n <= 50-> The grid is tiny. Even an O(m * n) approach that visits every cell is at most 2,500 operations. We have no performance concerns here, so the focus should be on correctness, not speed.0 <= image[i][j], color <= 65535-> Colors are non-negative integers. No special handling needed for negatives.0 <= sr < m, 0 <= sc < n-> The starting pixel is always valid. We do not need to check if the starting position is in bounds.
Approach 1: DFS (Recursive)
Intuition
The most natural way to think about flood fill is recursion. Start at the given pixel, repaint it, then ask each of its 4 neighbors: "Do you have the same original color?" If yes, recursively flood fill that neighbor too. If not, stop.
This is a standard 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 are doing a connected-component traversal, repainting every node we visit.
The one subtle point is avoiding infinite loops. When we repaint a pixel from originalColor to color, it no longer matches originalColor, so we will not visit it again. But what if color == originalColor? Then repainting does nothing, and the pixel still matches, so we would recurse into it again forever. The fix is simple: if the new color equals the original color, just return the image unchanged since there is nothing to do.
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 is already optimal in time, but the call stack can overflow on large grids. What if we replaced the implicit call stack with an explicit queue to control memory usage?
Approach 2: BFS (Iterative)
Intuition
Instead of exploring the grid recursively with DFS, we can use BFS with an explicit queue. The idea is identical: start at (sr, sc), repaint it, then explore all 4-connected neighbors of the same original color. The difference is purely mechanical. BFS explores outward in "rings" from the starting pixel, while DFS dives deep first. Both visit exactly the same set of pixels.
The advantage of BFS here is practical, not algorithmic. By using an explicit queue, we avoid the risk of stack overflow that comes with deep recursion. The time and space complexity remain the same, but the memory usage is on the heap (queue) rather than the call stack, which is typically much more limited.
BFS and DFS are both complete graph traversal algorithms. They guarantee that every node reachable from the starting node will be visited exactly once (as long as we mark nodes as visited). In this problem, "marking as visited" happens implicitly when we repaint a pixel. Once a pixel is changed from originalColor to color, it no longer satisfies the condition image[row][col] == originalColor, so it will never be enqueued again.
The key insight is that repainting serves double duty: it changes the pixel's color AND prevents revisiting. This is why we must handle the originalColor == color edge case upfront. If they are equal, repainting does not change anything, and the traversal has no way to distinguish visited from unvisited pixels.
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.