Flood Fill

25 min · floodFill()

One tap in a paint app can recolor a winding patch without touching the pixels right beside it in another patch. Your code gets to decide exactly where that color travels.

You're given a rectangular image image, a starting position (sr, sc), and a new color. A region is the set of pixels you can reach from the start by moving up, down, left, or right while staying on the start pixel's original color. Recolor every pixel in that region, then return the image.

A few ground rules:

Diagonal pixels don't connect.
Pixels with any color other than the start pixel's original color form a boundary.
If color already matches the original color, return the image unchanged.

Constraints

1 <= image.length <= 50
1 <= image[r].length <= 50
Every row has the same length.
0 <= image[r][c], color <= 65_536
0 <= sr < image.length
0 <= sc < image[0].length

Hints

Remember the first color

Save image[sr][sc] before changing anything. Every later decision compares a neighbor with that original color, not with the new one.

Walk the region

Treat each matching pixel as a node with at most four neighbors. A stack or queue can carry you through every reachable matching pixel.

Handle the no-op first

If the old and new colors match, stop immediately. Otherwise, recoloring a pixel can double as marking it visited.

Follow-up

Could you write the traversal iteratively so a long, narrow region never depends on your language's recursion limit?

Visible cases

Examples

Example 1

ready

Input: image = [ [ 1, 1, 1 ], [ 1, 1, 0 ], [ 1, 0, 1 ] ] sr = 1 sc = 1 color = 2
Expected: [ [ 2, 2, 2 ], [ 2, 2, 0 ], [ 2, 0, 1 ] ]
Why: the start's connected 1-region changes to 2; the diagonal 1 stays put

Example 2

ready

Input: image = [ [ 0, 0, 0 ], [ 0, 1, 1 ] ] sr = 1 sc = 1 color = 1
Expected: [ [ 0, 0, 0 ], [ 0, 1, 1 ] ]
Why: the requested color already matches, so the image is unchanged

Example 3

ready

Input: image = [ [ 3, 3, 8, 8 ], [ 3, 8, 8, 3 ], [ 3, 3, 3, 3 ] ] sr = 0 sc = 2 color = 5
Expected: [ [ 3, 3, 5, 5 ], [ 3, 5, 5, 3 ], [ 3, 3, 3, 3 ] ]
Why: only the connected patch of 8s is recolored

Interview signal

Asked at

AmazonGoogle

Visited-set stack fill — record the region first

A flood fill is a traversal that spreads through neighboring cells while a rule keeps matching. The direct version carries a stack plus a seen set. It explores every same-colored pixel connected to the start, then writes the new color into a copied image.

def flood_fill(
    image: list[list[int]], sr: int, sc: int, color: int
) -> list[list[int]]:
    original = image[sr][sc]
    result = [row[:] for row in image]
    stack = [(sr, sc)]
    seen: set[tuple[int, int]] = set()
 
    while stack:
        row, col = stack.pop()
        if (row, col) in seen or image[row][col] != original:
            continue
        seen.add((row, col))
        result[row][col] = color
 
        if row > 0:
            stack.append((row - 1, col))
        if row + 1 < len(image):
            stack.append((row + 1, col))
        if col > 0:
            stack.append((row, col - 1))
        if col + 1 < len(image[0]):
            stack.append((row, col + 1))
 
    return result

Time O(mn) — in the worst case, the region is the whole image. Space O(mn) for the copy, stack, and visited positions.

In-place grid DFS — let the new color mark visits

The sharper grid DFS treats the image as a graph and uses depth-first search to walk it. Once a pixel is recolored, it no longer equals original, so the image itself tells you that the pixel has been visited. That removes the separate set and copy.

There is one trap: when original == color, recoloring doesn't mark anything. Return before starting the traversal or the same neighbors can be added forever.

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])
    stack = [(sr, sc)]
    image[sr][sc] = color
 
    while stack:
        row, col = stack.pop()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                image[nr][nc] = color
                stack.append((nr, nc))
 
    return image

Time O(mn) — each pixel enters the stack at most once. Space O(mn) in the worst case for the explicit DFS stack.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayimage: int[][] · sr: int · sc: int · color: int

Expected

Run: visible + custom · Submit: full suite