Flood Fill (LeetCode 733)
A pixel grid image, sized m x n, holds a color per cell image[i][j]. You also get a starting position (sr, sc) and a replacement color. Simulate a flood fill (the paint-bucket tool) starting there:
- Recolor the starting pixel to
color. - Recolor every pixel reachable from it through a chain of up/down/left/right neighbors that all shared the starting pixel's original color.
- Stop once no more same-colored neighbor is left to recolor.
Return the grid after the fill.
Worked 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]](1, 1) (color 1), the fill spreads to every 1-colored pixel reachable through up/down/left/right steps and repaints them all to 2.
The pixel at (2, 2) keeps its original color 1, because it only touches the filled region diagonally, not horizontally or vertically.image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0[[0,0,0],[0,0,0]]⚖️Formal Constraints & Bounds
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], color < 2160 <= sr < m0 <= sc < n
Core Insight
In-place mutation prevents re-visitation, traversing the connected component in O(R · C) time.
Real-World Scenario & Production Applications
Paint bucket tool in graphics editors, bucket fill algorithms in image processing pipelines.
Step-by-Step Execution Trace Table
| Pixel (r, c) | Current Color | Action | Next Calls |
|---|---|---|---|
| (1, 1) | 1 | Repaint to 2 | (0,1), (2,1), (1,0), (1,2) |
| (0, 1) | 1 | Repaint to 2 | (0,0), (0,2) |
| (0, 0) | 1 | Repaint to 2 | None |
| (1, 2) | 0 | Color mismatch (0 != 1) | Return |
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]]| Pixel (r, c) | Current Color | Action | Next Calls |
|---|---|---|---|
| (1, 1) | 1 | Repaint to 2 | (0,1), (2,1), (1,0), (1,2) |
| (0, 1) | 1 | Repaint to 2 | (0,0), (0,2) |
| (0, 0) | 1 | Repaint to 2 | None |
| (1, 2) | 0 | Color mismatch (0 != 1) | Return |
| 1 | orig_color = image[sr][sc] |
| 2 | if orig_color == color: |
| 3 | return image |
| 4 | def dfs(r, c): |
| 5 | if (r, c) is outside the image or image[r][c] != orig_color: |
| 6 | return |
| 7 | image[r][c] = color |
| 8 | call dfs on each of the 4 neighbors |
| 9 | dfs(sr, sc) |
| 10 | return image |
Conceptual Narrative
Flood Fill performs connected-component traversal on a 2D grid, replacing all contiguous pixels of an initial color with a target replacement color.
🧭 Conceptual Foundation & Pattern Intuition
Starting from pixel (sr, sc) with color , flood fill visits all orthogonally adjacent pixels sharing color and overwrites them with . Traversal (DFS or BFS) treats the grid as an implicit graph with unit edges between identical neighboring colors.
🏟️ The Analogy: Paint Bucket Fill Tool
Clicking a pixel in Microsoft Paint with the Paint Bucket tool fills that pixel and all contiguous identical-color pixels with the new color until hitting different-color boundaries.
🔑 Why It Works
Checking image[sr][sc] == color upfront eliminates infinite recursion when the starting pixel already has the target color.
Infinite recursion on identical target color: When
image[sr][sc] == color, DFS recurses infinitely because the pixel never changes color. Guard withif orig == color: return image.Grid boundary condition errors: Forgetting boundary checks (
0 <= r < m and 0 <= c < n) before array indexing causesIndexError.Diagonal neighbor leakage: Problem allows orthogonal movements only (4-directional); accidentally including 8-directional diagonal movements corrupts fill regions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Repaint contiguous region of identical values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: image[r][c] is mutated directly to target color, preventing cycles.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I record
original_color = image[sr][sc]. Iforiginal_color == color, I return immediately. Otherwise, I run DFS from(sr, sc)in 4 directions, mutating valid cells tocolor. Runs in O(R · C) time and O(R · C) call stack space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: DFS/BFS from start pixel (sr, sc). Replaces connected pixels matching initial color with new color. Every connected cell visited once.
O(M · N) Auxiliary
Recursion stack reaches depth at most M · N in worst case.
T(M, N) = 4 · (M · N) = O(M · N)
Derivation Progression
if image[r][c] == origColor
Identifies valid candidate neighbors in O(1).
image[r][c] = color
Modifies pixel and marks visited simultaneously.
O(M · N) operations
Each pixel is recolored at most once.
Variable Definitions
Total number of rows in the image
Total number of columns in the image
Memory Architecture & Bounds
O(M · N) Call stack depth
O(1) In-place image mutation
O(1) Image reference
Boundary Best / Worst Cases
if image[sr][sc] == color.
.
if entire grid is original color.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "flood fill", "starting pixel (sr, sc)", "change color of all 4-directionally connected pixels". In-place DFS recoloring starting from seed coordinates.
. Time budget is linear.
Infinite Recursion Base Case Trap: If orig_color == color, recoloring produces identical values, causing infinite cycle recursion and stack overflow! Guard if orig_color == color: return image upfront.
Flood Fill (LeetCode 733)
A pixel grid image, sized m x n, holds a color per cell image[i][j]. You also get a starting position (sr, sc) and a replacement color. Simulate a flood fill (the paint-bucket tool) starting there:
- Recolor the starting pixel to
color. - Recolor every pixel reachable from it through a chain of up/down/left/right neighbors that all shared the starting pixel's original color.
- Stop once no more same-colored neighbor is left to recolor.
Return the grid after the fill.
Worked 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]](1, 1) (color 1), the fill spreads to every 1-colored pixel reachable through up/down/left/right steps and repaints them all to 2.
The pixel at (2, 2) keeps its original color 1, because it only touches the filled region diagonally, not horizontally or vertically.image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0[[0,0,0],[0,0,0]]⚖️Formal Constraints & Bounds
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], color < 2160 <= sr < m0 <= sc < n
Core Insight
In-place mutation prevents re-visitation, traversing the connected component in O(R · C) time.
Real-World Scenario & Production Applications
Paint bucket tool in graphics editors, bucket fill algorithms in image processing pipelines.
Step-by-Step Execution Trace Table
| Pixel (r, c) | Current Color | Action | Next Calls |
|---|---|---|---|
| (1, 1) | 1 | Repaint to 2 | (0,1), (2,1), (1,0), (1,2) |
| (0, 1) | 1 | Repaint to 2 | (0,0), (0,2) |
| (0, 0) | 1 | Repaint to 2 | None |
| (1, 2) | 0 | Color mismatch (0 != 1) | Return |
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]]| Pixel (r, c) | Current Color | Action | Next Calls |
|---|---|---|---|
| (1, 1) | 1 | Repaint to 2 | (0,1), (2,1), (1,0), (1,2) |
| (0, 1) | 1 | Repaint to 2 | (0,0), (0,2) |
| (0, 0) | 1 | Repaint to 2 | None |
| (1, 2) | 0 | Color mismatch (0 != 1) | Return |
| 1 | orig_color = image[sr][sc] |
| 2 | if orig_color == color: |
| 3 | return image |
| 4 | def dfs(r, c): |
| 5 | if (r, c) is outside the image or image[r][c] != orig_color: |
| 6 | return |
| 7 | image[r][c] = color |
| 8 | call dfs on each of the 4 neighbors |
| 9 | dfs(sr, sc) |
| 10 | return image |
Conceptual Narrative
Flood Fill performs connected-component traversal on a 2D grid, replacing all contiguous pixels of an initial color with a target replacement color.
🧭 Conceptual Foundation & Pattern Intuition
Starting from pixel (sr, sc) with color , flood fill visits all orthogonally adjacent pixels sharing color and overwrites them with . Traversal (DFS or BFS) treats the grid as an implicit graph with unit edges between identical neighboring colors.
🏟️ The Analogy: Paint Bucket Fill Tool
Clicking a pixel in Microsoft Paint with the Paint Bucket tool fills that pixel and all contiguous identical-color pixels with the new color until hitting different-color boundaries.
🔑 Why It Works
Checking image[sr][sc] == color upfront eliminates infinite recursion when the starting pixel already has the target color.
Infinite recursion on identical target color: When
image[sr][sc] == color, DFS recurses infinitely because the pixel never changes color. Guard withif orig == color: return image.Grid boundary condition errors: Forgetting boundary checks (
0 <= r < m and 0 <= c < n) before array indexing causesIndexError.Diagonal neighbor leakage: Problem allows orthogonal movements only (4-directional); accidentally including 8-directional diagonal movements corrupts fill regions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Repaint contiguous region of identical values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: image[r][c] is mutated directly to target color, preventing cycles.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I record
original_color = image[sr][sc]. Iforiginal_color == color, I return immediately. Otherwise, I run DFS from(sr, sc)in 4 directions, mutating valid cells tocolor. Runs in O(R · C) time and O(R · C) call stack space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: DFS/BFS from start pixel (sr, sc). Replaces connected pixels matching initial color with new color. Every connected cell visited once.
O(M · N) Auxiliary
Recursion stack reaches depth at most M · N in worst case.
T(M, N) = 4 · (M · N) = O(M · N)
Derivation Progression
if image[r][c] == origColor
Identifies valid candidate neighbors in O(1).
image[r][c] = color
Modifies pixel and marks visited simultaneously.
O(M · N) operations
Each pixel is recolored at most once.
Variable Definitions
Total number of rows in the image
Total number of columns in the image
Memory Architecture & Bounds
O(M · N) Call stack depth
O(1) In-place image mutation
O(1) Image reference
Boundary Best / Worst Cases
if image[sr][sc] == color.
.
if entire grid is original color.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "flood fill", "starting pixel (sr, sc)", "change color of all 4-directionally connected pixels". In-place DFS recoloring starting from seed coordinates.
. Time budget is linear.
Infinite Recursion Base Case Trap: If orig_color == color, recoloring produces identical values, causing infinite cycle recursion and stack overflow! Guard if orig_color == color: return image upfront.