A map editor’s paint-bucket recolors a click’s region on an integer raster: same old color, four neighbors, new fill. The intern walked neighbors from the click and never marked a cell. An 8×8 fixture in staging hung: two adjacent pixels of the old color bounced forever. They copied the raster and added a local seen set but still restarted a full flood from every pixel of that color. Staging returned in milliseconds. A million-pixel continent in production was still flooding when the request timed out.

Flood Fill asks to recolor the 4-connected blob that holds the start cell. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the DFS post owns the walk. Here we only care about four neighbor deltas, painting the start color we have already flooded, and bailing when that color already equals color.

The problem

Given an int[][] image, a start cell (sr, sc), and an int color, recolor the start pixel and every pixel you can reach in four directions — up, down, left, right — that still holds the start’s original color. Return the image. You may mutate it.

1 1 1
1 1 0
1 0 1
sr=1, sc=1, color=2  →

2 2 2
2 2 0
2 0 1     (2,2) stayed 1 — diagonal only

0 0 0
0 0 0
sr=0, sc=0, color=0  →  unchanged (start already color)

0
sr=0, sc=0, color=2  →  2

Note: Off-board is a wall. Bounds-check first, then skip any cell that is not the original color. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them. Do not walk diagonally unless the prompt says so. Number of Islands is the same 4-dir flood — that prompt counts how many times you start; this one paints one given start.

Copying the raster and restarting a flood from every matching pixel is the honest brute force

A neighbor walk with no mark never returns. From a pixel of the old color, step to a neighbor of the old color, step back, repeat. Staging’s hang was that bounce.

The honest version copies the image, marks inside one flood so the walk terminates, throws the marks away, and starts again from the next pixel of the old color — if that cell-set contains the start, paint those pixels in the copy. Correct. Quadratic.

int[][] floodFillRestart(int[][] image, int sr, int sc, int color) {
    int m = image.length;
    int n = image[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int old = image[sr][sc];
    int[][] out = new int[m][];
    for (int r = 0; r < m; r++) {
        out[r] = image[r].clone();
    }
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (image[r][c] == old) {
                Set<Integer> cells = new HashSet<>();
                collect(image, r, c, old, dirs, cells);
                if (cells.contains(sr * n + sc)) {
                    for (int packed : cells) {
                        out[packed / n][packed % n] = color;
                    }
                }
            }
        }
    }
    return out;
}

void collect(int[][] image, int r, int c, int old, int[][] dirs, Set<Integer> cells) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) {
        return;
    }
    if (image[r][c] != old || !cells.add(r * image[0].length + c)) {
        return;
    }
    for (int[] d : dirs) {
        collect(image, r + d[0], c + d[1], old, dirs, cells);
    }
}

At an 8×8 fixture this is a rounding error. On one blob of V pixels of the start color you restart a V-cell flood V times: you paid a full walk per matching pixel for a question that only needs one walk from the start.

Early-out, then recolor the component

If image[sr][sc] already equals color, return the image. Otherwise save the old color and flood from the start. The flood writes old → color so a neighbor cannot bounce back onto a cell you already painted.

1 1 1
1 1 0
1 0 1     start (1,1) old=1 color=2

paint (1,1)
  (1,0) 1 → paint, then (0,0), (2,0)
  (1,2) 0 skip
  (0,1) 1 → paint, then (0,2)
  (2,1) 0 skip

2 2 2
2 2 0
2 0 1     (2,2) never entered — not 4-connected

Four deltas, bounds-check, skip any cell that is not old. Mutation is allowed, so skip a second boolean[][]. The Java is that walk; the guard is bounds plus “not the old color.”

int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int old = image[sr][sc];
    if (old == color) {
        return image;
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    flood(image, sr, sc, old, color, dirs);
    return image;
}

void flood(int[][] image, int r, int c, int old, int color, int[][] dirs) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != old) {
        return;
    }
    image[r][c] = color;
    for (int[] d : dirs) {
        flood(image, r + d[0], c + d[1], old, color, dirs);
    }
}

Time is O(mn) — each cell is painted at most once, and each painted cell looks at four neighbors. Space is O(mn) for the call stack on a solid blob. A million-pixel region is a million frames; an iterative ArrayDeque is the same bound without blowing the JVM stack.

Note: Bail when old == color. Skip the early-out, and the mutating DFS paints a cell to the same value, so the “not old” guard never fires, and two neighbors bounce until the stack blows.

What interviewers usually poke next

  • Iterative flood. Same paint, an ArrayDeque of cells. BFS (offer / poll) or explicit DFS (push / pop). Not java.util.Stack. Not ArrayList.remove(0).
  • Number of Islands. Same 4-dir flood; count how many times you start instead of recoloring one given start.
  • Max Area of Island. Count cells inside the flood, keep the max. Same walk, different return.
  • Surrounded Regions. Flood from the border instead of from a click; the interior leftover is the capture.
  • Read-only grid, or diagonals. If mutation is forbidden, a boolean[][] seen is the mark. Diagonals are eight deltas — ask before you edit the table.

You are done with this problem when you can say, out loud, why an unmarked neighbor walk never returns, why copying the raster and restarting a flood from every matching pixel is quadratic, and why one flood from the start (after the early-out) is enough.