AAlgoLoopSpaced repetition for LeetCode
EASYBFS / DFSLeetCode ↗

Flood Fill

The key idea

Flood fill is a connected-component repaint. Remember the start pixel's original color, then explore only neighbors that still hold that original color, recoloring as you go. If the new color already equals the original, do nothing — otherwise the repainted cells would be revisited forever.

Problem

You are given an image represented by an m x n integer grid image, where image[i][j] is the pixel value. You are also given three integers sr, sc, and color. Perform a flood fill starting from the pixel image[sr][sc]. To do this, change the color of the starting pixel and of every pixel 4-directionally connected to it that shares the same color as the starting pixel, and of every pixel connected to those, and so on — replacing each such pixel's value with color. Return the modified image.

Constraints

Examples

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]]
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Output: [[0,0,0],[0,0,0]]
Input: image = [[1,1,0],[1,0,1]], sr = 0, sc = 0, color = 2 Output: [[2,2,0],[2,0,1]]

Complexity

Time: O(m * n) Space: O(m * n)

See the full solution

410310
Step-by-step visualization
Start free →

More BFS / DFS problems