Flood Fill

Difficulty: Easy

Problem

You receive a picture stored as a 2D grid of integer colors, plus a starting cell (sr, sc) and a replacement color. Recolor the starting cell together with every cell reachable from it by steps up, down, left or right through cells that have the starting cell's ORIGINAL color. This is just the bucket-fill tool in a paint program. Return the recolored grid.

Example

Input: image = [[0,0,3],[0,3,3],[1,0,3]], sr = 0, sc = 0, color = 5
Output: [[5,5,3],[5,3,3],[1,0,3]]
Explanation: The three 0s linked to (0, 0) through up/down/left/right steps become 5. The 0 in the bottom row stays: it is boxed in by a 1 and a 3, so no chain of 4-directional steps reaches it.

Brute-force approach

There is no meaningful brute force vs optimal split. Flood fill IS the DFS you built in Graph Foundations, applied directly to the grid. Graph problems skip straight to the optimal approach.

Optimal approach

Key insight: The region to repaint is exactly the connected component of the old color containing (sr, sc). Paint each cell BEFORE spreading: a repainted cell no longer matches the old color, so the image itself becomes the visited set. One guard (old == color) removes the only infinite loop.

Save the start cell's color, then DFS outward from (sr, sc): paint every in-bounds cell that still shows the old color, and let each painted cell spread to its four neighbors. The paint itself marks cells visited.

Steps

Save old = image[sr][sc]: the color that defines the region
Guard: if old == color, return the image untouched, painting would change nothing, and without this the flood never terminates
fill(r, c) stops at out-of-bounds cells and at cells that don't show old (that's the region boundary AND the visited check)
Paint image[r][c] = color FIRST, the in-place visited mark
Spread with fill(r-1, c), fill(r+1, c), fill(r, c-1), fill(r, c+1); kick off with fill(sr, sc) and return the image

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) worst-case recursion depth

Pseudocode

function floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if ____:
        return image
    
    function fill(r, c):
        if (r, c) is outside the grid:
            return
        if image[r][c] != ____:
            return
        
        ____ = color
        
        fill(r-1, c)
        fill(r+1, c)
        fill(r, c-1)
        ____
    
    fill(sr, sc)
    return image

Hints

The guard: which situation makes painting a no-op, yet leaves every painted cell still matching 'old' forever? Compare the two colors before doing anything else.
A cell belongs to the region only while it still shows the color you saved at the very start, compare against that saved value.
Paint the CURRENT cell by assigning into the image, writing the new color is also your visited mark, so it happens before any spreading.
Up, down, left... one direction is missing. The fourth spread moves along the row: fill(r, c+1).

Complexity questions

The image has rows × cols cells. What is the time complexity of flood fill?

O(rows × cols): each cell is painted at most once, and re-entries are rejected in O(1). The 'four branches' fear is an illusion: a cell only spreads if it still shows the old color, and painting makes that a one-time event. Each cell is painted at most once and entered at most a handful of times (once per neighbor) as a cheap rejected call, O(rows × cols) total.

What is the worst-case space complexity, and what shape of region causes it?

O(rows × cols): a snake-shaped region winding through the whole grid makes the recursion go that deep. Painting in place saves the visited SET, but not the call STACK. Picture one long serpentine corridor of the old color threading through every cell: fill recurses one cell deeper for each, so the stack can hold all rows × cols frames at once.

Why does this solution need no visited set, when every DFS in foundations carried one?

Painting IS the marking: a repainted cell fails the image[r][c] != old check, so the flood never re-enters it. Grid-graphs are full of cycles, every 2x2 block is one, so SOMETHING must stop revisits. Here the marking happens in place: once a cell turns the new color, it can never match old again. The visited set didn't vanish; it moved into the image itself.

Could you flood fill with BFS (a queue) instead of DFS recursion?

Yes: any traversal that covers the whole connected component works; DFS is simply less code here. Enqueue (sr, sc), then pop cells, paint them, and enqueue same-old-color neighbors: same O(rows × cols), same final image. Flood fill only needs 'touch every cell in the component'; visit ORDER is irrelevant. BFS even avoids deep recursion, at the cost of managing the queue by hand.

Check your understanding of Flood Fill

You click cell (sr, sc) with the paint bucket. Which cells end up repainted?

The start cell plus all cells connected to it 4-directionally that share its original color. Flood fill repaints one connected REGION, not one color. A far-away cell with the same color stays untouched unless an unbroken 4-directional chain of same-color cells links it to the start. That's exactly how the paint bucket behaves in an image editor.

In the example ([[0,0,3],[0,3,3],[1,0,3]], start (0,0)), why does the 0 in the bottom row, at (2,1), stay a 0?

It only touches the painted region diagonally, and 4-directional connectivity has no diagonal edges. Cell (2,1) holds a 0 just like the region, but its up-neighbor (1,1) is 3, its left-neighbor (2,0) is 1 and its right-neighbor (2,2) is 3. It meets the painted (1,0) only at a corner, and a corner is not an edge in the grid-graph, so no path of same-colored cells reaches (2,1).

In Graph Foundations every DFS carried a visited set. What plays that role in flood fill?

The paint itself: once repainted, a cell no longer matches the old color, so the DFS never re-enters it. This is the elegant bit: painting a cell IS marking it visited. A repainted cell fails the 'still shows the old color' test forever after, so the flood can't loop back into it. In-place marking, exactly as promised in foundations.

Suppose the new color equals the old color (say both are 1) and there's no guard. What happens?

Infinite recursion: painted cells STILL match the old color, so the flood revisits them forever. Painting 1 over 1 changes nothing, so every 'visited' cell still passes the == old check, and neighbors keep re-entering each other until the stack blows up. One early return (if old == color, return the image) removes the trap entirely.

Which foundation pattern is flood fill an instance of?

DFS over the grid-graph: exploring one connected component. Cells are nodes, 4-directional touching is the edges, and the region to repaint is one connected component. A DFS from the start cell visits exactly that component: the same flood you animated in Graph Foundations, now holding a paintbrush.