Problem statement

Given an image grid, a start pixel (sr, sc) and a new color, flood fill: recolor the start pixel and every pixel connected 4-directionally to it that shares its original color. Return the modified 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]]

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: New color equals the old — nothing changes.

Constraints

• 1 <= rows, cols <= 7
• 0 <= pixel values, color <= 9
• sr/sc are inside the grid.

Hints for Flood Fill

1. Hint 1

   DFS or BFS from (sr, sc), only expanding into pixels matching the ORIGINAL color.

2. Hint 2

   If the new color equals the original, return immediately to avoid an infinite loop.

How to solve Flood Fill

Recolouring a connected region is a plain graph traversal on the grid: start at the seed pixel and spread to any 4-directional neighbour that still carries the original colour. The one trap is when the new colour equals the original — then repainting changes nothing, and the traversal has no way to tell visited pixels from unvisited ones, so it loops forever.

Approach

1. Read the original colour at (sr, sc).
2. If it already equals the target colour, return the image unchanged.
3. Push the seed onto a stack (or queue) and recolour it.
4. Pop a pixel and, for each of its four neighbours that is in bounds and still holds the original colour, recolour it and push it.
5. Continue until the frontier is empty.

Why it works

Recolouring a pixel the moment it is pushed doubles as the "visited" mark, since the original colour is the only thing the traversal expands into — so each pixel enters the frontier at most once and the traversal terminates. It reaches exactly the connected component of the seed under 4-adjacency, which is precisely the region the problem defines. The early return is not an optimisation but a correctness requirement: without it the visited mark is invisible and the search revisits pixels forever.

Complexity

• Time — O(rows · cols)
• Space — O(rows · cols)

Pitfalls

• The color == original early return is mandatory — without it the traversal never terminates.
• Expand only into pixels matching the original colour, not the new one.
• Mark (recolour) on push, not on pop, or the same pixel is queued many times.
• Connectivity is 4-directional; including diagonals fills too much.

Reference solution

Python

from typing import List

def floodFill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
    old = image[sr][sc]
    if old == color:
        return image
    stack = [(sr, sc)]
    while stack:
        i, j = stack.pop()
        if i < 0 or j < 0 or i >= len(image) or j >= len(image[0]) or image[i][j] != old:
            continue
        image[i][j] = color
        stack.extend([(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)])
    return image

Java

public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int original = image[sr][sc];
    if (original == color) return image;
    int rows = image.length, cols = image[0].length;
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{sr, sc});
    image[sr][sc] = color;
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == original) {
                image[nr][nc] = color;
                stack.push(new int[]{nr, nc});
            }
        }
    }
    return image;
}

C++

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int original = image[sr][sc];
    if (original == color) return image;
    int rows = (int) image.size(), cols = (int) image[0].size();
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    vector<pair<int, int>> stack;
    stack.push_back(make_pair(sr, sc));
    image[sr][sc] = color;
    while (!stack.empty()) {
        pair<int, int> cell = stack.back();
        stack.pop_back();
        for (int d = 0; d < 4; d++) {
            int nr = cell.first + dr[d], nc = cell.second + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == original) {
                image[nr][nc] = color;
                stack.push_back(make_pair(nr, nc));
            }
        }
    }
    return image;
}

JavaScript

var floodFill = function(image, sr, sc, color) {
    const old = image[sr][sc];
    if (old === color) return image;
    const stack = [[sr, sc]];
    while (stack.length > 0) {
        const cell = stack.pop();
        const i = cell[0], j = cell[1];
        if (i < 0 || j < 0 || i >= image.length || j >= image[0].length || image[i][j] !== old) continue;
        image[i][j] = color;
        stack.push([i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]);
    }
    return image;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy