Flood Fill: DFS on a Grid

You know the paint bucket tool in image editors? Click a region, and every connected pixel of the same color changes to the new color. That is exactly what LeetCode 733: Flood Fill asks you to implement. It is one of the cleanest introductions to DFS on a grid, and the pattern it teaches shows up in dozens of harder problems.

The problem

You are given an m x n grid called image, where image[i][j] represents the color of pixel (i, j). You are also given a starting pixel (sr, sc) and a color value. Perform a flood fill starting from pixel (sr, sc): change the color of the starting pixel and every pixel connected to it (horizontally or vertically) that shares the same original color to the new color. Return the modified image.

The approach

This is a textbook recursive DFS problem. The algorithm is:

1. Record the original color at (sr, sc)
2. If the original color already equals the new color, return the image as-is (nothing to do)
3. Call a DFS function starting at (sr, sc)
4. In the DFS: change the current pixel to the new color, then recurse on all four neighbors (up, down, left, right) that still have the original color

The key insight is that changing a pixel's color before recursing on its neighbors serves double duty: it fills the pixel and marks it as visited. You never visit the same pixel twice because its color no longer matches the original.

def flood_fill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    original = image[sr][sc]
    if original == color:
        return image

    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original:
            return
        image[r][c] = color
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    dfs(sr, sc)
    return image

The early return when original == color is important. Without it, the DFS would never terminate because changing a pixel to the same color it already has means the "visited" check (image[r][c] != original) never triggers.

Step-by-step walkthrough

Let's trace through the classic example: image = [[1,1,1],[1,1,0],[1,0,1]], starting at pixel (1, 1) with new color 2. Watch how the DFS explores every connected pixel with value 1 and changes it to 2.

Notice how the DFS naturally stops at boundaries: the 0s act as walls that the recursion cannot cross. The pixel at (2, 2) has value 1 but is completely surrounded by 0s, so the flood fill never reaches it. This is exactly how the paint bucket tool works: it only fills the connected region, not every pixel of the same color in the entire image.

Complexity analysis

Time: In the worst case, every pixel in the grid has the same color and is connected to the starting pixel. The DFS visits each pixel exactly once, so the total work is proportional to the number of pixels.

Space: The recursion depth in the worst case is m * n (imagine a grid that is one long snake of same-colored pixels). Each recursive call adds a frame to the call stack.

The building blocks

DFS on a grid

Flood fill is built on one fundamental building block: DFS with in-place marking on a 2D grid. The pattern looks like this:

1. Check bounds: is (r, c) inside the grid?
2. Check condition: does this pixel meet our criteria (same color as original)?
3. Process: change the pixel's color
4. Recurse: visit all four neighbors

This same skeleton powers Number of Islands, Max Area of Island, Surrounded Regions, and Pacific Atlantic Water Flow. The only thing that changes between these problems is what you check in step 2 and what you do in step 3. Once you can write the flood fill DFS from memory, you have the template for all of them.

The neighbor generation pattern is always the same:

for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        dfs(nr, nc)

This direction array approach is cleaner than writing four separate if-statements, and it extends naturally to eight directions if a problem requires diagonal movement.

Edge cases

Original color equals new color. If the starting pixel already has the target color, return immediately. Without this check, the DFS enters an infinite loop because pixels never appear "visited" (their color never changes from the original).

Single pixel. A 1x1 grid is valid input. The DFS changes just that one pixel and returns. No neighbors to visit.

Starting pixel on an edge or corner. The bounds check in the DFS handles this naturally. A corner pixel has only two valid neighbors, an edge pixel has three, and an interior pixel has four. The if r < 0 or r >= rows or c < 0 or c >= cols: return guard takes care of all cases uniformly.

From understanding to recall

Flood fill is one of those problems where the solution feels obvious once you see it. The DFS is short, the logic is clean, and the recursion is natural. But can you write it from scratch in two minutes during an interview?

The details matter: remembering to check if the original color equals the new color, getting the bounds check right, knowing to change the color before recursing rather than after. These are not conceptual hurdles. They are recall challenges. You understand the algorithm, but under pressure, small details slip.

Spaced repetition fixes this. You write the flood fill DFS from memory at increasing intervals until the pattern is automatic. When a grid DFS problem shows up, you are not reconstructing the algorithm from first principles. You are just writing code you have written many times before.

Related posts

• Number of Islands - Uses the same DFS flood fill to count connected components in a grid
• Max Area of Island - Extends flood fill to track the size of each region
• Surrounded Regions - Flood fill from the border to identify regions that should not be captured