Definition
- Flood fill – a traversal from a starting cell that recolors every orthogonally connected cell sharing the starting cell's original color to a new color.
- No-op guard – if the new color equals the original color, return immediately to avoid infinite recursion or reprocessing.
- Visited marker – when new and old colors differ, the new color itself acts as the visited marker because a recolored cell no longer matches the original.
- DFS approach – recursively recolor the current cell and its four neighbours.
- BFS approach – use a queue to spread the recoloring level by level, preferred for large connected regions to avoid stack overflow.
At the National Bank of India, a risk heat map lets an analyst click a contiguous block of same-status cells and reclassify them to a new status. Flood fill spreads the new status across the connected region and stops at cells of a different status. The equal-status guard makes reclassifying to the same value a safe no-op rather than an infinite loop.
Understanding the Concepts
What is the Flood Fill problem?
The problem gives a grid of pixel colors, a starting pixel at position (sr, sc), and a new color. The task is to repaint the starting pixel and every orthogonally connected pixel of the same original color with the new color, then return the modified grid. This is a single-source traversal that recolors a connected region.
package com.bank.service;
public class FloodFill {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image; // no-op guard
dfs(image, sr, sc, originalColor, newColor);
return image;
}
private void dfs(int[][] image, int r, int c, int original, int newColor) {
if (r < 0 || c < 0 || r >= image.length || c >= image[0].length
|| image[r][c] != original) {
return;
}
image[r][c] = newColor;
dfs(image, r + 1, c, original, newColor);
dfs(image, r - 1, c, original, newColor);
dfs(image, r, c + 1, original, newColor);
dfs(image, r, c - 1, original, newColor);
}
public static void main(String[] args) {
int[][] image = {
{1, 1, 1},
{1, 1, 0},
{1, 0, 1}
};
new FloodFill().floodFill(image, 1, 1, 2);
for (int[] row : image) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
}
}
2 2 2
2 2 0
2 0 1
Why is the no-op guard essential?
If the new color equals the original color, repainting a cell does not change its value, so it still matches the original color condition. Without the guard, the DFS would process the same cells indefinitely, causing infinite recursion and a stack overflow. The guard checks if (originalColor == newColor) return image; before starting the traversal.
package com.bank.service;
public class NoOpGuardDemo {
// Without guard: floodFill(image, 0, 0, 1) where image[0][0] == 1
// dfs visits (0,0), sets it to 1 (no change), recurses to neighbours
// neighbours still match original (1), recurse back to (0,0)
// infinite loop => StackOverflowError
public static void main(String[] args) {
int[][] image = {{1, 1}, {1, 1}};
// With guard: returns immediately, no infinite loop
new FloodFill().floodFill(image, 0, 0, 1);
System.out.println("No-op guard prevents infinite recursion.");
System.out.println("image[0][0] = " + image[0][0]);
}
}
No-op guard prevents infinite recursion.
image[0][0] = 1
How does the new color serve as the visited marker?
When the new color differs from the original, recoloring a cell changes its value so it no longer matches the original color condition. This means a recolored cell will fail the image[r][c] != original check and will not be processed again. The new color itself acts as the visited marker, eliminating the need for a separate visited matrix.
package com.bank.service;
public class VisitedMarkerExplanation {
// Before: image[r][c] == original (match)
// After: image[r][c] == newColor (no match, because newColor != original)
// So recolored cells are never revisited.
public static void main(String[] args) {
int[][] image = {{1, 1, 0}, {1, 0, 0}};
System.out.println("Before: image[0][0] = " + image[0][0]);
new FloodFill().floodFill(image, 0, 0, 3);
System.out.println("After: image[0][0] = " + image[0][0]);
System.out.println("Cell no longer matches original (1), so it won't be revisited.");
}
}
Before: image[0][0] = 1
After: image[0][0] = 3
Cell no longer matches original (1), so it won't be revisited.
How is this different from Number of Islands?
| Feature | Flood Fill | Number of Islands |
|---|---|---|
| Start | single specified cell | sweep all cells |
| Goal | recolor one connected region | count all connected components |
| Guard needed | yes (new == old) | no (overwrite always changes '1' to '0') |
| Return value | modified grid | count of islands |
| Cells affected | one region only | all land cells |
package com.bank.service;
public class FloodFillVsIslands {
public static void main(String[] args) {
System.out.println("Flood Fill: single source, recolor one region.");
System.out.println("Islands: sweep all cells, count components.");
System.out.println("Both use DFS/BFS traversal on a grid.");
}
}
How do you implement it with BFS?
BFS uses a queue to avoid deep recursion. Enqueue the starting cell, mark it with the new color, and process the queue. For each cell, check its four neighbours and enqueue any that match the original color.
package com.bank.service;
import java.util.LinkedList;
import java.util.Queue;
public class FloodFillBFS {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int original = image[sr][sc];
if (original == newColor) return image;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{sr, sc});
image[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 && nc >= 0 && nr < image.length && nc < image[0].length
&& image[nr][nc] == original) {
image[nr][nc] = newColor;
queue.add(new int[]{nr, nc});
}
}
}
return image;
}
public static void main(String[] args) {
int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
new FloodFillBFS().floodFill(image, 1, 1, 2);
for (int[] row : image) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
}
}
2 2 2
2 2 0
2 0 1
What are the edge cases?
Edge cases include the no-op case where the new color equals the original, a single-cell grid, a starting cell with no matching neighbours, and a grid where the entire grid is the same color. The no-op case is the most critical because it causes infinite recursion without the guard.
package com.bank.service;
public class FloodFillEdgeCases {
public static void main(String[] args) {
FloodFill solver = new FloodFill();
// Single cell
int[][] single = {{5}};
solver.floodFill(single, 0, 0, 9);
System.out.println("Single cell: " + single[0][0]);
// No matching neighbours
int[][] noMatch = {{1, 2}, {3, 4}};
solver.floodFill(noMatch, 0, 0, 7);
System.out.println("Only (0,0) changed: " + noMatch[0][0] + ", " + noMatch[0][1]);
// Entire grid same color
int[][] allSame = {{1, 1}, {1, 1}};
solver.floodFill(allSame, 0, 0, 3);
System.out.println("All changed: " + allSame[0][0] + ", " + allSame[1][1]);
}
}
Single cell: 9
Only (0,0) changed: 7, 2
All changed: 3, 3
What are common mistakes?
The most common mistake is forgetting the no-op guard when new equals old, causing infinite recursion. Another mistake is checking the original color against image[sr][sc] after starting the DFS, at which point the starting cell has already been recolored.
Wrong code:
// WRONG: no guard, infinite recursion when newColor == original
public int[][] floodFillBad(int[][] image, int sr, int sc, int newColor) {
dfs(image, sr, sc, image[sr][sc], newColor); // no guard
return image;
}
Correct code:
// CORRECT: guard against no-op
public int[][] floodFillGood(int[][] image, int sr, int sc, int newColor) {
int original = image[sr][sc];
if (original == newColor) return image; // guard
dfs(image, sr, sc, original, newColor);
return image;
}
What should a senior engineer know?
A senior engineer knows that flood fill is the building block for paint bucket tools, region selection in image editors, and contiguous status changes in dashboards. They choose BFS for large regions to avoid stack overflow and know that the no-op guard is the single most important correctness detail. In production at National Bank of India, the risk heat map uses flood fill to reclassify contiguous blocks of same-risk cells when an analyst updates a region's risk level.
package com.bank.service;
public class SeniorFloodFillNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" 1. No-op guard is the #1 correctness detail.");
System.out.println(" 2. BFS for large regions avoids stack overflow.");
System.out.println(" 3. Same pattern as paint bucket, region selection.");
System.out.println(" 4. Time: O(region size), Space: O(region size).");
}
}
Visual Overview
Flood Fill from (1,1) with newColor=2 Before: After: ┌───┬───┬───┐ ┌───┬───┬───┐ │ 1 │ 1 │ 1 │ │ 2 │ 2 │ 2 │ ├───┼───┼───┤ ├───┼───┼───┤ │ 1 │ 1 │ 0 │ │ 2 │ 2 │ 0 │ 0 is different color, stops ├───┼───┼───┤ ├───┼───┼───┤ │ 1 │ 0 │ 1 │ │ 2 │ 0 │ 1 │ (2,2) not connected to region └───┴───┴───┘ └───┴───┴───┘ DFS traversal from (1,1): ┌──────────────────────────────────┐ │ (1,1) color=1 -> set to 2 │ │ ├─ (2,1) color=0 -> STOP │ │ ├─ (0,1) color=1 -> set to 2 │ │ │ ├─ (0,0) color=1 -> set 2 │ │ │ └─ (0,2) color=1 -> set 2 │ │ ├─ (1,2) color=0 -> STOP │ │ └─ (1,0) color=1 -> set to 2 │ │ └─ (2,0) color=1 -> set 2 │ └──────────────────────────────────┘
Key Takeaway
Flood Fill recolors a connected region of a grid starting from a given cell, repainting every orthogonally connected cell that shares the starting cell's original color. The solution records the original color, runs a DFS or BFS from the start, and recolors each matching cell while spreading to its four neighbours.
The single most important detail is the no-op guard: if the new color equals the original color, return immediately. Without this guard, a recolored cell still matches the original condition, so the traversal would revisit it indefinitely, causing infinite recursion. With distinct colors, a recolored cell no longer matches the original, so the new color itself acts as the visited marker.
The time and space are both proportional to the size of the connected region. For very large regions, BFS is preferred to avoid deep recursion. The problem is essentially the island traversal but seeded from one arbitrary cell instead of sweeping the whole grid.
At the National Bank of India, the risk heat map lets analysts reclassify a contiguous block of same-risk cells by clicking one cell. Flood fill spreads the new risk level across the connected region, and the no-op guard ensures that reclassifying to the same level is a safe no-op. This pattern is the same one behind paint bucket tools and region selection in image editors.
Remember one sentence: from the start cell, DFS or BFS recolors all connected same-color cells, and the no-op guard when new equals old prevents infinite recursion.
---