Flood Fill
Problem link: https://leetcode.com/problems/flood-fill/
Problem Statement
You are given an image represented by an m x n grid. Each cell represents the color of a pixel.
You are also given a starting pixel (sr, sc) and a new color.
Perform a flood fill: change the color of the starting pixel and all connected pixels with the same original color (4-directionally) to the new color.
Input
image[][] → grid of colors sr, sc → starting pixel color → new color
Output
Return the modified image after flood fill.
Example
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]]
Explanation
Start from (1,1). Traverse all connected cells with same color and update them.
Brute Force
Intuition
Repeatedly scan the entire grid to update colors based on neighbors until no more changes occur.
Approach
Iterate through the entire grid multiple times. For each cell, if it's the target color and adjacent to an already-filled cell, update it. Stop when a full pass results in no changes.
Dry Run
A 3x3 grid might require multiple full passes to propagate the color from one corner to another.
Code (Java)
Complexity Analysis
In the worst case (a long snake-like path), you might only fill one new pixel per full grid scan.
Optimal Solution
Intuition
Treat the grid as a graph where each pixel is a node and edges exist between 4-directional neighbors of the same color. A single traversal (DFS or BFS) visits each connected node exactly once.
Approach
- Identify the original color at (sr, sc).
- If original color is already the new color, return immediately to avoid infinite loops.
- Use a queue (BFS) or recursion (DFS) to visit all adjacent pixels with the original color.
- Change each visited pixel's color to the new color.
Dry Run
Queue: [(1,1)] -> Pop (1,1), Color it 2, Push neighbors with color 1 -> Queue: [(0,1), (1,0), (2,1)]...
Code (Java)
// DFS Approach
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int original = image[sr][sc];
if (original == color) return image;
dfs(image, sr, sc, original, color);
return image;
}
private void dfs(int[][] image, int r, int c, int original, int color) {
if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] != original)
return;
image[r][c] = color;
dfs(image, r + 1, c, original, color);
dfs(image, r - 1, c, original, color);
dfs(image, r, c + 1, original, color);
dfs(image, r, c - 1, original, color);
}
}
// BFS Approach
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int startColor = image[sr][sc];
if (startColor == color) return image;
int m = image.length, n = image[0].length;
int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{sr, sc});
image[sr][sc] = color; // Mark as visited by changing color
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int[] d : dir) {
int i = curr[0] + d[0];
int j = curr[1] + d[1];
if (i >= 0 && i < m && j >= 0 && j < n && image[i][j] == startColor) {
image[i][j] = color;
q.offer(new int[]{i, j});
}
}
}
return image;
}
}
Complexity Analysis
Time: Every pixel is processed at most once. Space: In the worst case, the stack (DFS) or queue (BFS) holds O(m*n) pixels.
Quick Revision (Brute Force)
- Repeated grid scans
- O((N*M)^2) complexity
Quick Revision (Optimal)
- Single traversal (DFS/BFS)
- Edge Case: Original color == New color (must handle to avoid infinite loop)
- 4-directional connectivity