Flood Fill
Easy · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix
Problem
An image is given as an m x n integer grid image, where each value is a pixel color. You are also given a starting pixel (sr, sc) and a new color.
Perform a flood fill: recolor the starting pixel, then every pixel connected to it horizontally or vertically through pixels of the same original color, to color.
Return the image after the fill.
Examples
Input: image = [[2,2,0],[0,2,3],[2,0,2]], sr = 0, sc = 0, color = 5 Output: [[5,5,0],[0,5,3],[2,0,2]]
The three connected 2s reachable from the corner turn to 5; the 2s in the bottom row are not connected to them.
Input: image = [[4,4],[4,4]], sr = 1, sc = 1, color = 4 Output: [[4,4],[4,4]]
The new color matches the old one, so nothing changes.
Input: image = [[0,0,0],[0,7,0],[0,0,0]], sr = 2, sc = 2, color = 1 Output: [[1,1,1],[1,7,1],[1,1,1]]
Every 0 is connected around the 7, so all eight turn to 1.
Constraints
- m == len(image), n == len(image[i])
- 1 <= m, n <= 50
- 0 <= image[i][j], color < 2^16
- 0 <= sr < m
- 0 <= sc < n
Approaches
- Baseline: grow the region scan by scan — time O((m · n)²), space O(m · n)
Follow-up
What if the image were 10^4 x 10^4? A recursive search would overflow the call stack, so keep the explicit stack (or a queue). To fill many regions in a row, as a paint program does, scanline filling paints whole runs of a row at once and pushes far fewer cells.
Related problems
Start free on Cariara · Coding problems · System design studio
