DSA problem
Flood Fill
You are given an m x n grid image representing an image where image[i][j] is the integer color of that pixel, along with a starting pixel (sr, sc) and a target color. Perform a flood fill: starting at (sr, sc), change the color of every pixel connected 4-directionally to the start (up, down, left, right) and sharing the start pixel's original color to the new color. Return the modified image.
The key subtlety is that the comparison is always against the start pixel's ORIGINAL color, not the current color of a neighbor. If you naively recolor before recursing, that is still correct — every visited cell now holds the new color and will never re-match the original color, which doubles as a natural visited marker.
There is, however, an important degenerate case: if the new color equals the start pixel's original color, every cell already matches, so recoloring would be a no-op but a naive DFS would loop forever because nothing changes to break the recursion. Always early-return when newColor == startColor.
The optimal solution is a single DFS (or BFS) from (sr, sc). Recurse into a neighbor only when it is in bounds AND its current value equals the start pixel's original color. At the start of each call, recolor the cell. The algorithm visits each cell of the connected component exactly once, giving O(m * n) time in the worst case and O(m * n) recursion-stack space for a fully connected grid.
Examples
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]]image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0[[0,0,0],[0,0,0]]image = [[0,0,0],[1,0,0]], sr = 1, sc = 0, color = 2[[0,0,0],[2,0,0]]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
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.