Definition
- Flood Fill repaints a connected region of same-color cells starting from a given cell.
- DFS approach recursively visits each same-color neighbor, repainting before recursing to prevent revisits.
- BFS approach uses a queue, enqueuing and repainting neighbors before dequeuing.
- Critical guard is the early return when newColor == originalColor, which prevents infinite recursion or infinite queueing.
- Time is O(rows * cols) in the worst case; space is O(region size) for the stack or queue.
Think of the National Bank of India plotting a map of branches where each cell is a region with a risk rating. The risk team taps one region rated "medium" and says "reclassify this whole connected medium zone as high." The change spreads outward from the tapped region to every touching region that was also medium, like paint spreading across connected tiles, stopping where the rating is different.
Understanding the Concepts
What is the Flood Fill problem?
Flood Fill takes a 2D grid, a starting cell (row, col), and a new color. It repaints the starting cell and every cell connected to it through up, down, left, and right neighbors that shares the original color of the starting cell. Cells with a different color act as boundaries. This is exactly how the paint-bucket tool works in image editors.
package com.bank.service;
public class RiskZoneEscalator {
public int[][] floodFill(int[][] grid, int sr, int sc,
int newColor) {
int originalColor = grid[sr][sc];
if (originalColor == newColor) return grid; // critical guard
dfs(grid, sr, sc, originalColor, newColor);
return grid;
}
private void dfs(int[][] grid, int r, int c,
int original, int newColor) {
if (r < 0 || r >= grid.length
|| c < 0 || c >= grid[0].length
|| grid[r][c] != original) {
return;
}
grid[r][c] = newColor; // repaint before recursing
dfs(grid, r - 1, c, original, newColor);
dfs(grid, r + 1, c, original, newColor);
dfs(grid, r, c - 1, original, newColor);
dfs(grid, r, c + 1, original, newColor);
}
}
Why is the early return guard essential?
If the new color is the same as the original color, every cell you repaint still matches the original, so the recursion never stops. The DFS version recurses forever and overflows the stack. The BFS version enqueues the same cells endlessly. The one-line guard if (originalColor == newColor) return grid; prevents both.
// WITHOUT guard: infinite recursion when newColor == originalColor
// grid[r][c] = newColor; // cell still matches originalColor!
// dfs(grid, r-1, c, ...) // neighbor is the cell we just repainted!
// ... → StackOverflowError
// WITH guard: return immediately, no work needed
if (originalColor == newColor) return grid;
How does the DFS approach work step by step?
At each cell, check bounds and color match. If valid, repaint the cell and recurse into all four neighbors. Repainting before recursing is what prevents revisiting: neighbors check the grid value and see the new color, which does not match the original, so they stop.
Grid (original=1, newColor=2):
1 1 0
1 0 0
0 0 0
Start: (0,0)
(0,0)=1 → paint 2, recurse up, down, left, right
up: out of bounds
down: (1,0)=1 → paint 2, recurse
down: (2,0)=0 → stop (not original)
right: (1,1)=0 → stop
right: (0,1)=1 → paint 2, recurse
right: (0,2)=0 → stop
down: (1,1)=0 → stop
Result:
2 2 0
2 0 0
0 0 0
How does the BFS approach work?
Enqueue the start cell and repaint it. For each dequeued cell, check its four neighbors. If a neighbor is in bounds and matches the original color, repaint it and enqueue it. Repainting at enqueue time ensures each cell is enqueued at most once.
public int[][] floodFillBFS(int[][] grid, int sr, int sc,
int newColor) {
int original = grid[sr][sc];
if (original == newColor) return grid;
java.util.Queue<int[]> queue = new java.util.LinkedList<>();
queue.offer(new int[]{sr, sc});
grid[sr][sc] = newColor;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < grid.length
&& nc >= 0 && nc < grid[0].length
&& grid[nr][nc] == original) {
grid[nr][nc] = newColor;
queue.offer(new int[]{nr, nc});
}
}
}
return grid;
}
How do DFS and BFS compare for Flood Fill?
| Aspect | DFS | BFS |
|--------|-----|-----|
| Data structure | Call stack (implicit) | Queue (explicit) |
| Fill order | Deep first, then backtrack | Level by level (outward rings) |
| Stack overflow risk | Yes on large regions | No |
| Code length | Shorter (recursive) | Longer (queue loop) |
| Time | O(region size) | O(region size) |
What are edge cases?
- Start cell already has the new color: return immediately (the critical guard).
- Single-cell grid: repaint just that cell.
- Entire grid is the same color: the fill covers every cell.
- Start cell has a unique color not shared by any neighbor: only the start cell is repainted.
// Edge case: start cell is the only one with original color
// Grid: 1 0
// 0 0
// Start: (0,0), newColor = 2
// Result: 2 0
// 0 0 (only the start cell changed)
What are common mistakes?
The first and most dangerous mistake is forgetting the early return guard when newColor == originalColor. The second mistake is marking cells at dequeue time in BFS, causing cells to be enqueued multiple times. The third mistake is checking diagonal neighbors, which the problem does not count.
// WRONG: mark at dequeue time
int[] cell = queue.poll();
grid[cell[0]][cell[1]] = newColor; // too late!
// CORRECT: mark at enqueue time
grid[nr][nc] = newColor;
queue.offer(new int[]{nr, nc});
What about using a separate visited array?
If you cannot modify the grid, use a boolean visited array instead of repainting. The logic is the same, but you check visited[r][c] instead of grid[r][c] != original. After the traversal, paint all visited cells with the new color.
boolean[][] visited = new boolean[rows][cols];
// Use visited to track instead of modifying grid during traversal
What should a senior engineer know?
At the National Bank of India, the risk team maintained a geographic grid where each cell carried a risk code. When a fraud cluster was confirmed in one zone, the system escalated the entire connected block of zones sharing that code. Flood Fill did exactly that, and the early-return guard made it safe to re-trigger without looping, which mattered because the risk team sometimes clicked the same zone twice. The same pattern applies to image processing, region labeling, and minesweeper reveal logic.
Visual Overview
Flood Fill DFS from (0,0), original=1, new=2 ================================================ Before: After: 1 1 0 2 2 0 1 0 0 2 0 0 0 0 0 0 0 0 ┌────────────────────────────────────────┐ │ (0,0)=1 → paint 2 │ │ ├── up: out of bounds │ │ ├── down: (1,0)=1 → paint 2 │ │ │ ├── down: (2,0)=0 → stop │ │ │ ├── right: (1,1)=0 → stop │ │ │ └── left: out of bounds │ │ ├── left: out of bounds │ │ └── right: (0,1)=1 → paint 2 │ │ ├── right: (0,2)=0 → stop │ │ └── down: (1,1)=0 → stop │ └────────────────────────────────────────┘ Critical guard: ┌───────────────────────────────────┐ │ if (original == newColor) return; │ │ Prevents infinite recursion! │ └───────────────────────────────────┘
Key Takeaway
Flood Fill repaints a connected region of same-color cells starting from a given cell. The DFS version recursively visits each matching neighbor, repainting before recursing so that repainted cells stop matching and prevent revisits. The BFS version uses a queue and repaints at enqueue time to avoid duplicate processing.
The single most important guard is the early return when the new color equals the original color. Without it, every repainted cell still matches the original, so the recursion or queueing never stops. This one-line check is the difference between a correct solution and an infinite loop.
Both approaches run in O(region size) time because each cell in the connected region is visited exactly once. The DFS version is shorter but risks stack overflow on large regions; the BFS version uses a queue and avoids deep recursion. The same pattern powers paint-bucket tools, image region labeling, and minesweeper reveal logic.
At the National Bank of India, the risk team used Flood Fill to escalate an entire connected block of geographic zones sharing a risk code when a fraud cluster was confirmed. The early-return guard made the escalation safe to re-trigger, which mattered because the team sometimes clicked the same zone twice.
Remember one sentence: repaint before recursing so repainted cells stop matching, and always guard against newColor equaling originalColor to prevent infinite loops.
---