How does flood fill work, and how do you implement it?

Reported as a question a former Zalando interviewer used to ask, taken from Cracking the Coding Interview. The usual programming-interview statement is the same as LeetCode 733, Flood Fill. This is an older interviewer example, not a 2022–2026 candidate diary, but it is first-hand and the prompt is standard enough to implement honestly.

Problem. You have a grid of integer pixel colors, a start cell (sr, sc), and a new color. Recolor every cell that is 4-connected (up, down, left, right) to the start cell through cells of the start cell's original color. Return the grid.

Approach. Record old = image[sr][sc]. If old already equals the new color, return the grid unchanged — otherwise a DFS or BFS would loop. Then search from the start and write the new color onto every reachable cell of color old. Time and extra memory are O(rows × cols) in the worst case (the whole grid is one region). BFS with a queue avoids a deep recursion on a large blob; DFS is the same idea in fewer lines.

import java.util.*;

public class FloodFill {
    static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int rows = image.length, cols = image[0].length;
        int[][] out = new int[rows][cols];
        for (int r = 0; r < rows; r++) out[r] = Arrays.copyOf(image[r], cols);
        int old = out[sr][sc];
        if (old == newColor) return out;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {sr, sc});
        out[sr][sc] = newColor;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        while (!q.isEmpty()) {
            int[] p = q.removeFirst();
            for (int k = 0; k < 4; k++) {
                int r = p[0] + dr[k], c = p[1] + dc[k];
                if (r >= 0 && r < rows && c >= 0 && c < cols && out[r][c] == old) {
                    out[r][c] = newColor;
                    q.add(new int[] {r, c});
                }
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        System.out.println(Arrays.deepToString(floodFill(image, 1, 1, 2)));
        // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
    }
}

Verified with OpenJDK 21.0.13: it prints [[2, 2, 2], [2, 2, 0], [2, 0, 1]], which is the standard LeetCode example, and it does not mutate the input array.

Edge cases and follow-ups. The start color already equals the new color; a one-cell grid; a region that touches the border; 8-connected versus 4-connected (ask); mutating in place versus returning a copy.