Flood Fill (LeetCode 733)

An image is stored as a 2D grid of integers, int[][] image, where each number is a pixel’s color. You are given a starting pixel (sr, sc) and a new color. Recolor the starting pixel, and every pixel connected to it horizontally or vertically that has the same original color, to color. This is the “paint bucket” tool from drawing programs. Return the image.

For example, starting at the top-left pixel (0, 0) with color = 7:

Before        After
3 3 0 3       7 7 0 3
3 0 0 0       7 0 0 0
3 3 3 0       7 7 7 0

Six pixels with color 3 are connected to (0, 0), and all of them become 7. The 3 in the top-right corner is not connected to them, since only horizontal and vertical neighbors count, so it stays 3.

The Solution

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalStartColor = image[sr][sc];
        if (originalStartColor == color) {
            return image;  // nothing to recolor, and the fill would never stop
        }
        floodHelper(image, sr, sc, color, originalStartColor);
        return image;
    }

    private void floodHelper(int[][] image, int row, int col, int color, int originalStartColor) {
        if (row < 0 || col < 0 || row >= image.length || col >= image[0].length
                || image[row][col] != originalStartColor) {
            return;
        }
        image[row][col] = color;  // recoloring also marks the cell as visited
        floodHelper(image, row + 1, col, color, originalStartColor);
        floodHelper(image, row, col + 1, color, originalStartColor);
        floodHelper(image, row - 1, col, color, originalStartColor);
        floodHelper(image, row, col - 1, color, originalStartColor);
    }
}

How the Recursion Solves It

The recursive approach rests on one observation: the region to fill is the starting pixel plus the regions to fill from each of its neighbors. So floodHelper only ever handles a single pixel and hands the rest of the work to four recursive calls, one per neighbor.

Base cases. A call stops immediately, without doing anything, if:

the pixel is outside the image, or
the pixel does not have the original color. Either it was never part of the region, or it has already been recolored.

Recursive case. Otherwise, the pixel belongs to the region and has not been filled yet. We recolor it, then call floodHelper on its four neighbors: down, right, up and left.

The key is to trust the recursion. When floodHelper is called on a neighbor, we do not need to follow everything it does. We only need to know that when it returns, every pixel reachable from that neighbor through original-color pixels has been recolored. Since every pixel of the region is reachable from the starting pixel this way, the first call fills the whole region.

Why it always stops. Every recursive call that does real work recolors one pixel, and a recolored pixel never matches the original color again. The region has a finite number of pixels, so only a finite number of calls can do work. Every other call hits a base case and returns right away.

Why This Is a Depth-First Search

Think of the image as a graph: each pixel is a vertex, and each pair of horizontally or vertically adjacent pixels is joined by an edge. Flood fill is then a graph traversal that visits every vertex reachable from the starting pixel through original-color pixels.

This version is a depth-first search (DFS). Each call tries “down” first and follows that direction as far as it can, going deeper and deeper, before it ever tries “right,” “up” or “left.” Only when a path is blocked in every direction does the recursion return to an earlier pixel and try its next neighbor.

Here is the order in which the example’s pixels get recolored, starting from (0, 0):

1 6 . .
2 . . .
3 4 5 .

The fill goes down from (0, 0) to (1, 0) and (2, 0), then right along the bottom row to (2, 2). Only after that path is blocked does it unwind all the way back to (0, 0) and recolor its right neighbor, (0, 1), sixth, even though (0, 1) is right next to the starting pixel. That is depth-first behavior: go deep first, then back up.

The call stack acts as DFS’s stack. Each active call is a pixel on the current path, and returning from a call is backing up one step. At the moment (2, 2) is recolored, five calls are active, one for each pixel on the path from (0, 0).

A breadth-first search (BFS) would fill the same pixels in a different order: first every pixel 1 step from the start, then every pixel 2 steps away, and so on, spreading out in rings. (0, 1) would be filled second. Both searches recolor the same region, so both solve the problem.

Why There’s No `visited` Array

Number of Islands keeps a separate boolean[][] visited array. Flood fill does not need one, because recoloring marks the pixel. Once a pixel has the new color, it no longer matches originalStartColor, so the base case stops any later call that reaches it. The image itself records which pixels have been visited.

Why the Early Return Matters

if (originalStartColor == color) {
    return image;
}

This check is more than a shortcut. Without it, if the new color equals the original color, recoloring a pixel changes nothing, so the pixel still looks unfilled. Two neighboring pixels would keep calling floodHelper on each other forever, and the program would crash with a StackOverflowError. In testing, removing this check crashed even on a 2×2 image.

When the colors are equal, the correct answer is the unchanged image anyway, so we return it right away.

Notes From My First Version

My first version had a comment at the top of floodFill:

//Advice, creater a helper function that helps us keep track of
//former color [during first iteration] & intended color.

The original floodFill signature has no parameter for the original color, and every recursive call needs it to tell which pixels belong to the region. A helper method with an extra parameter carries that value through the recursion.

My first version also checked the color again right before recoloring:

//this will always be true at this stage of the algo
int currColor = image[row][col];
if (currColor == originalStartColor) {
    image[row][col] = color;
}

As the comment says, the check is always true: any pixel without the original color has already returned in the base case. The cleaned-up version recolors directly.

Complexity

Let the image have $m$ rows and $n$ columns.

Time: $\Theta(mn)$ in the worst case. Each pixel in the region is recolored once. Each recolored pixel makes 4 calls, and every call does constant work outside its own recursive calls, so the total work is proportional to the size of the region. In the worst case, the region is the whole image, which has $mn$ pixels.

Space: $\Theta(mn)$ in the worst case. There is no extra array, but the recursion uses the call stack. A region that winds through every pixel can make the recursion $\Theta(mn)$ calls deep. LeetCode’s images are at most 50×50, so the recursion is at most 2,500 calls deep, which fits comfortably on Java’s default stack.

flood-fill.html