Flood Fill

easyGraphs: BFS / DFS128 stepsJava · Python · C++

Starting from one pixel, repaint it and every connected pixel of the same original colour. DFS spreads in four directions and only continues into cells that still have the original colour.

▶ Watch the animated trace

Traced input: 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]]. Original problem: neetcode.io/problems/flood-fill

Complexity

BestO(1)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each pixel is painted once; recursion can be as deep as the region.

Key idea

Pixels of the original colour that touch each other form one region.
Paint a cell before recursing so it isn't visited again.
If the new colour equals the original, return immediately, or the DFS never ends.

Common mistakes

Missing the same-colour check: infinite recursion.
Moving diagonally; only 4 directions count.
Forgetting bounds checks before reading image[r][c].

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int original = image[sr][sc];
    if (original == color) {
        return image;
    }
    fill(image, sr, sc, original, color);
    return image;
}

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

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def floodFill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
    original = image[sr][sc]
    if original == color:
        return image

    def fill(r: int, c: int) -> None:
        if r < 0 or c < 0 or r >= len(image) or c >= len(image[0]) or image[r][c] != original: return
        image[r][c] = color
        for dr, dc in DIRS: fill(r + dr, c + dc)

    fill(sr, sc)
    return image

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
void fill(vector<vector<int>>& image, int r, int c, int original, int color);

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int original = image[sr][sc];
    if (original == color) {
        return image;
    }
    fill(image, sr, sc, original, color);
    return image;
}

void fill(vector<vector<int>>& image, int r, int c, int original, int color) {
    if (r < 0 || c < 0 || r >= (int)image.size() || c >= (int)image[0].size() || image[r][c] != original) return;
    image[r][c] = color;
    for (auto& d : DIRS) fill(image, r + d[0], c + d[1], original, color);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Same colour Nothing changes; the early return prevents an infinite loop.	`image = [[0, 0, 0], [0, 0, 0]], sr = 0, sc = 0, color = 0`	`[[0, 0, 0], [0, 0, 0]]`
Single pixel Only one cell to paint.	`image = [[5]], sr = 0, sc = 0, color = 3`	`[[3]]`
Diagonals don't connect The bottom-right 1 touches only diagonally.	`image = [[1, 0], [0, 1]], sr = 0, sc = 0, color = 9`	`[[9, 0], [0, 1]]`