#733 Flood Fill

frequently reported atAmazon Microsoft Google

the problem

In plain words

Starting from pixel (sr, sc), recolour it and every pixel connected to it (4 directions) that has the same original colour. Return the image.

in image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

out [[2,2,2],[2,2,0],[2,0,1]]

The bottom-right 1 isn't connected to the start (only diagonally).

in image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

out [[0,0,0],[0,0,0]]

1 ≤ m, n ≤ 50
0 ≤ image[i][j], color < 2¹⁶

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGrid flood fill

It's the paint-bucket tool. Repainting a pixel also marks it visited — except when the new colour equals the old one, so handle that case first.

solutions

From brute force to optimal

Paint, then recurse into the 4 neighbours that still have the original colour.

If the start already has the new colour, return.
paint(r, c): stop if out of bounds or not the original colour; else repaint and recurse 4 ways.

timeO(m · n)

Each pixel is repainted at most once.

spaceO(m · n)

Recursion depth can reach the number of pixels.

javajava.util.*

1class Solution {2    public int[][] floodFill(int[][] image, int sr, int sc, int color) {3        int start = image[sr][sc];4        if (start != color) paint(image, sr, sc, start, color); // same colour → nothing to do (and no infinite loop)5        return image;6    }7 8    private void paint(int[][] image, int r, int c, int start, int color) {9        if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] != start) return;10        image[r][c] = color; // repainting doubles as the "visited" mark11        paint(image, r + 1, c, start, color);12        paint(image, r - 1, c, start, color);13        paint(image, r, c + 1, start, color);14        paint(image, r, c - 1, start, color);15    }16}

Same fill, ring by ring, without recursion.

Repaint the start and enqueue it.
Poll; repaint and enqueue every neighbour with the original colour.

timeO(m · n)

Each pixel is enqueued at most once.

spaceO(m · n)

Queue size in the worst case.

javajava.util.*

1class Solution {2    public int[][] floodFill(int[][] image, int sr, int sc, int color) {3        int start = image[sr][sc];4        if (start == color) return image;5        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};6        Deque<int[]> queue = new ArrayDeque<>();7        image[sr][sc] = color;8        queue.offer(new int[] {sr, sc});9        while (!queue.isEmpty()) {10            int[] cell = queue.poll();11            for (int[] d : dirs) {12                int nr = cell[0] + d[0], nc = cell[1] + d[1];13                if (nr < 0 || nc < 0 || nr >= image.length || nc >= image[0].length) continue;14                if (image[nr][nc] != start) continue;15                image[nr][nc] = color;16                queue.offer(new int[] {nr, nc});17            }18        }19        return image;20    }21}

in the room

How to say it in the interview

talk track

Point out the start == color edge case before coding — it's the infinite-recursion trap.

traps

Without the same-colour guard, the DFS keeps "repainting" the same pixels forever (StackOverflowError).

what they ask next

Follow-ups

Can you avoid recursion?

Yes: the BFS version (or an ArrayDeque used as a stack) does the same fill on the heap, so a big region can't overflow the call stack.

before you submit

Edge cases to test

New colour equals the start colour → return the image unchanged (without the guard the DFS never stops).
1×1 image → just that pixel changes.
Pixels that touch only diagonally stay as they are.

practise next