Problem 22.2 · Depth-First SearchEasy

Flood Fill

PatternGraph DFS and Flood Fill Matrix Traversal

What it teaches: The paint-bucket tool: DFS over same-coloured neighbours.

Practise it on judges as “Flood Fill”.

The problem

Starting from pixel (sr, sc), recolour it and every pixel connected to it (up/down/left/right) that has the same original colour to color. Return the image.

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Constraints

1 ≤ rows, cols ≤ 50

Pattern clues in the wording

→ Recolour a connected region

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        return image;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	image = [[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	image = [[0,0,0],[0,0,0]] sr = 0 sc = 0 color = 0	[[0,0,0],[0,0,0]]

From slow to fast

Approaches

1. DFS · O(rows × cols)

DFS

Time O(rows × cols) Space O(rows × cols)

Remember the original colour; DFS recolouring cells that still have it.

Approach 1

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old != color) fill(image, sr, sc, old, color);
        return image;
    }

    private void fill(int[][] img, int r, int c, int old, int color) {
        if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
        img[r][c] = color;
        fill(img, r + 1, c, old, color); fill(img, r - 1, c, old, color);
        fill(img, r, c + 1, old, color); fill(img, r, c - 1, old, color);
    }
}

Verdict: The recoloured cell acts as its own visited mark.

Before you submit

Edge cases and common mistakes

Test these inputs

New colour equals the old colour
Single pixel

Mistakes people make

Missing the same-colour check, which recurses forever.

Interview

Follow-up questions

How do real paint programs avoid deep recursion on huge images?

Command Palette

The problem

Approaches

DFS

Edge cases and common mistakes

Follow-up questions