Flood Fill

EasyGraph BFS/DFSGrokkingJuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given an m x n grid image of pixel colors, a starting pixel (sr, sc), and a new color. Recolor the starting pixel, along with every pixel you can reach from it by moving up, down, left, or right through pixels of the starting pixel's original color. Diagonal moves don't count. Return the modified image. If the starting pixel already has the new color, return the image unchanged.

Examples

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

before

after

The corner 1 is cut off by the two 0s.

Every 1 connected to the center becomes 2. The 1 in the bottom-right corner touches that region only diagonally, so it keeps its color.

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

The starting pixel is already 0, so nothing changes.

Constraints

m == image.length, n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 2^16
0 <= sr < m and 0 <= sc < n

Hints

Hint 1

Which pixels change? Think of the image as a set of connected regions.

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Treat the grid as a graph where each pixel connects to its four neighbors, and run a depth-first search (DFS) from the start. Remember the original color, recolor the start, and push it onto a stack. Pop a pixel, and for each in-bounds neighbor that still has the original color, recolor it and push it. Recoloring doubles as the visited mark, so no separate set is needed. An explicit stack also stays clear of Python's recursion limit on a 50 x 50 grid of one color.

Time

O(m * n)

Space

O(m * n)

Pitfall

Skipping the early return when the start already has the new color loops forever: every recolored pixel still matches the original color, so the search keeps revisiting the same pixels. Checking the original color after overwriting the start pixel fails the same way.

Solutions

class Solution {
    public 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[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> stack = new ArrayDeque<>();
        image[sr][sc] = color;
        stack.push(new int[]{sr, sc});
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            for (int[] d : dirs) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && r < rows && c >= 0 && c < cols && image[r][c] == original) {
                    image[r][c] = color;
                    stack.push(new int[]{r, c});
                }
            }
        }
        return image;
    }
}

class Solution:
    def floodFill(self, image, sr: int, sc: int, color: int):
        original = image[sr][sc]
        if original == color:
            return image
        rows, cols = len(image), len(image[0])
        image[sr][sc] = color
        stack = [(sr, sc)]
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                    image[nr][nc] = color
                    stack.append((nr, nc))
        return image