Flood fill algo
Problem Statement
Given a 2D grid representing an image, a starting pixel (sr, sc), and a new color, perform a flood fill. Change the color of the starting pixel and all connected pixels (up, down, left, right) that have the same original color to the new color.
Example:
- Input:
image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2 - Output:
[[2,2,2],[2,2,0],[2,0,1]]
Noob-Friendly Explanation
You know the "paint bucket" tool in MS Paint or any drawing app? You click on one area and it fills ALL connected same-colored pixels with the new color. That's exactly what flood fill does!
Starting from the clicked pixel, you look up, down, left, and right. If a neighbor has the same color as the original, paint it too, then check ITS neighbors, and so on. It spreads like water flooding an area.
Approach 1: Brute Force (BFS)
Intuition
Use BFS starting from the given pixel. Add the pixel to a queue, change its color, then process all neighbors with the same original color.
Algorithm
- If the starting pixel already has the new color, return (no change needed).
- Store the original color.
- Use a queue starting with (sr, sc).
- Change the color of the starting pixel.
- For each pixel in the queue, check all 4 neighbors. If they have the original color, change them and add to queue.
import java.util.LinkedList;
import java.util.Queue;
public class FloodFillBFS {
public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
int rows = image.length;
int cols = image[0].length;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{sr, sc});
image[sr][sc] = newColor;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int i = 0; i < 4; i++) {
int newRow = cell[0] + dx[i];
int newCol = cell[1] + dy[i];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
&& image[newRow][newCol] == originalColor) {
image[newRow][newCol] = newColor;
queue.add(new int[]{newRow, newCol});
}
}
}
return image;
}
public static void main(String[] args) {
int[][] image = {{1,1,1},{1,1,0},{1,0,1}};
int[][] result = floodFill(image, 1, 1, 2);
for (int[] row : result) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
// Output: 2 2 2 / 2 2 0 / 2 0 1
}
}Complexity Analysis
- Time Complexity: O(M × N) — in the worst case, every pixel is visited once.
- Space Complexity: O(M × N) — for the queue in the worst case.
Approach 2: Optimal (DFS — Recursive)
Intuition
Use DFS recursion. It's simpler and more concise. Start from the pixel, change its color, then recursively fill all 4 neighbors that have the original color.
Algorithm
- If starting pixel already has the new color, return.
- Store original color and call recursive DFS.
- In DFS: change current pixel color, then recurse on all 4 valid neighbors with original color.
public class FloodFillDFS {
public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
dfs(image, sr, sc, originalColor, newColor);
return image;
}
static void dfs(int[][] image, int row, int col, int originalColor, int newColor) {
if (row < 0 || row >= image.length || col < 0 || col >= image[0].length) {
return;
}
if (image[row][col] != originalColor) {
return;
}
image[row][col] = newColor;
dfs(image, row - 1, col, originalColor, newColor); // up
dfs(image, row + 1, col, originalColor, newColor); // down
dfs(image, row, col - 1, originalColor, newColor); // left
dfs(image, row, col + 1, originalColor, newColor); // right
}
public static void main(String[] args) {
int[][] image = {{1,1,1},{1,1,0},{1,0,1}};
int[][] result = floodFill(image, 1, 1, 2);
for (int[] row : result) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
// Output: 2 2 2 / 2 2 0 / 2 0 1
}
}Complexity Analysis
- Time Complexity: O(M × N) — each pixel is visited at most once.
- Space Complexity: O(M × N) — for the recursion stack in the worst case.