LeetCode 733: Flood Fill
Recolor the connected component containing the starting pixel using depth-first search.
Problem Restatement
We are given an image represented as a 2D grid of integers.
Each integer is a pixel color.
We are also given:
sr
sc
color
sr and sc describe the starting pixel:
image[sr][sc]
We need to perform a flood fill from that starting pixel.
Flood fill changes the starting pixel and every pixel connected to it with the same original color.
Connection is only 4-directional:
up
down
left
right
Diagonal pixels are not connected.
At the end, return the modified image. The official statement defines the image as a 2D integer array and asks us to recolor the starting pixel plus all 4-directionally connected pixels with the same original color.
Input and Output
| Item | Meaning |
|---|---|
| Input | image, sr, sc, color |
| Output | The modified image |
| Starting pixel | image[sr][sc] |
| Connected pixels | Adjacent vertically or horizontally |
| Recolored pixels | Only pixels connected to the start with the same original color |
Example function shape:
def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
...
Examples
Example 1
image = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 1],
]
sr = 1
sc = 1
color = 2
The starting pixel is:
image[1][1] == 1
So the original color is 1.
We recolor all 1 pixels connected to (1, 1) through up, down, left, or right moves.
The result is:
[
[2, 2, 2],
[2, 2, 0],
[2, 0, 1],
]
The bottom-right 1 stays unchanged because it is diagonal from a filled region and cannot be reached through 4-directional moves.
Example 2
image = [
[0, 0, 0],
[0, 0, 0],
]
sr = 0
sc = 0
color = 0
The original color is already 0.
The new color is also 0.
The image does not need to change:
[
[0, 0, 0],
[0, 0, 0],
]
This case matters because without an early return, DFS may keep revisiting pixels forever.
First Thought: Traverse the Connected Region
This is a grid connectivity problem.
Each pixel is like a node in a graph.
There is an edge between two pixels if they are adjacent up, down, left, or right.
We need to visit the connected component that starts at (sr, sc) and contains only pixels with the same original color.
Depth-first search is a natural fit.
Key Insight
Save the original color first:
original = image[sr][sc]
Then DFS should only enter a cell if:
- The row is inside the grid.
- The column is inside the grid.
- The cell still has the original color.
When a valid cell is found, recolor it immediately.
That recoloring also marks the cell as visited.
So we do not need a separate visited set, as long as original != color.
Algorithm
- Store the original color at the starting pixel.
- If the original color equals the new color, return
image. - Define a DFS function
dfs(r, c). - In
dfs, stop if(r, c)is out of bounds. - Stop if
image[r][c] != original. - Otherwise, set
image[r][c] = color. - Recursively visit the four neighbors.
- Return the modified image.
Correctness
The DFS starts at the given pixel (sr, sc). Since this pixel has the original color, it is part of the region that must be recolored.
Whenever DFS visits a pixel, it first checks that the pixel lies inside the image and has the original color. Therefore, DFS never recolors a pixel outside the image, and it never recolors a pixel with a different color.
After a pixel is recolored, DFS recursively explores its four neighbors. Therefore, any pixel reachable from the start through a path of 4-directionally adjacent original-color pixels will eventually be visited and recolored.
Pixels outside this connected component cannot be reached by such a path, so DFS never recolors them.
Thus the algorithm recolors exactly the required connected component and returns the correct image.
Complexity
Let m be the number of rows and n be the number of columns.
| Metric | Value | Why |
|---|---|---|
| Time | O(m * n) |
In the worst case, every pixel is visited once |
| Space | O(m * n) |
The recursion stack can contain many pixels in the worst case |
The image is modified in place.
Implementation
class Solution:
def floodFill(
self,
image: list[list[int]],
sr: int,
sc: int,
color: int,
) -> list[list[int]]:
rows = len(image)
cols = len(image[0])
original = image[sr][sc]
if original == color:
return image
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows:
return
if c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
Code Explanation
We first read the grid size:
rows = len(image)
cols = len(image[0])
Then we save the starting color:
original = image[sr][sc]
This is the only color that may be replaced.
If the new color is the same as the original color, there is no work to do:
if original == color:
return image
This also prevents repeated recursion over already unchanged cells.
The DFS rejects invalid positions:
if r < 0 or r >= rows:
return
if c < 0 or c >= cols:
return
It also rejects cells that are not part of the original-color component:
if image[r][c] != original:
return
When a cell is valid, we recolor it:
image[r][c] = color
Then we visit the four adjacent cells:
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
Testing
def run_tests():
s = Solution()
image = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 1],
]
assert s.floodFill(image, 1, 1, 2) == [
[2, 2, 2],
[2, 2, 0],
[2, 0, 1],
]
image = [
[0, 0, 0],
[0, 0, 0],
]
assert s.floodFill(image, 0, 0, 0) == [
[0, 0, 0],
[0, 0, 0],
]
image = [[1]]
assert s.floodFill(image, 0, 0, 2) == [[2]]
image = [
[1, 0, 1],
[0, 1, 0],
[1, 0, 1],
]
assert s.floodFill(image, 1, 1, 2) == [
[1, 0, 1],
[0, 2, 0],
[1, 0, 1],
]
print("all tests passed")
run_tests()
| Test | Why |
|---|---|
| Standard 3 by 3 image | Checks connected component fill |
| New color equals original color | Checks early return |
| Single cell | Minimum image size |
| Diagonal same-color pixels | Confirms diagonals are not connected |