Definition
- Island – a connected component of land cells ('1') that are linked horizontally or vertically, surrounded by water ('0').
- Flood fill – a DFS or BFS from a land cell that marks every connected land cell as visited so the same component is never counted twice.
- Sweep – iterate over every cell in the grid; when an unvisited land cell is found, increment the island count and launch a flood fill.
- In-place marking – overwrite visited land cells with '0' to avoid a separate visited matrix, but this mutates the input.
- Time complexity – O(rows times cols) because each cell is visited at most a constant number of times.
At the National Bank of India, Rajesh has a map of branch locations where land cells are branches and water cells are gaps. Connected branches form a regional cluster. He sweeps the map, and each time he hits a branch he has not counted, he adds one cluster and walks outward marking every connected branch so the same cluster is never counted twice.
Understanding the Concepts
What is the Number of Islands problem?
The problem gives a two-dimensional grid of characters where '1' represents land and '0' represents water. An island is a group of land cells connected horizontally or vertically. The task is to count how many distinct islands exist in the grid. This is a connected-components counting problem on a grid graph.
package com.bank.service;
public class NumberOfIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
count++;
dfs(grid, r, c);
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length
|| grid[r][c] == '0') {
return;
}
grid[r][c] = '0'; // mark as visited
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
public static void main(String[] args) {
NumberOfIslands solver = new NumberOfIslands();
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
System.out.println("Number of islands: " + solver.numIslands(grid));
}
}
Number of islands: 3
Why does flood fill work for counting islands?
Flood fill works because each island is a connected component. When we find an unvisited land cell, we know it belongs to a new island. By flood-filling the entire connected component as visited, we ensure that no cell in this island triggers a new count. The total number of flood fills we launch equals the number of islands.
In the banking domain, Rajesh counts how many independent service clusters exist in the branch coverage map. Each flood fill consumes one cluster.
package com.bank.service;
public class FloodFillExplanation {
// When we find grid[r][c] == '1' (unvisited land):
// 1. This is a NEW island => count++
// 2. Flood-fill marks ALL connected land as visited
// 3. No cell in this island will trigger count++ again
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0'},
{'0', '0', '1'}
};
// Cell (0,0): land, count=1, flood-fill marks (0,0) and (0,1)
// Cell (0,1): already '0' (visited), skip
// Cell (1,2): land, count=2, flood-fill marks (1,2)
// Result: 2 islands
System.out.println("Expected: 2 islands");
}
}
How do you implement it with BFS instead of DFS?
BFS uses a queue instead of recursion. When a land cell is found, add it to the queue and mark it visited. Then process the queue: for each cell, check its four neighbours and enqueue any unvisited land cells. BFS avoids deep recursion, which is important for very large grids where DFS might cause a stack overflow.
package com.bank.service;
import java.util.LinkedList;
import java.util.Queue;
public class NumberOfIslandsBFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
count++;
bfs(grid, r, c, rows, cols);
}
}
}
return count;
}
private void bfs(char[][] grid, int r, int c, int rows, int cols) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
grid[r][c] = '0';
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : directions) {
int nr = cell[0] + d[0];
int nc = cell[1] + d[1];
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols
&& grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.add(new int[]{nr, nc});
}
}
}
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0'},
{'1', '0', '0', '1'},
{'0', '0', '1', '1'}
};
System.out.println("Islands (BFS): " + new NumberOfIslandsBFS().numIslands(grid));
}
}
Islands (BFS): 3
How is DFS different from BFS for this problem?
| Feature | DFS | BFS |
|---|---|---|
| Data structure | recursion stack | explicit queue |
| Traversal order | explores one branch deeply before backtracking | explores all neighbours at current distance first |
| Stack overflow risk | yes, on large grids | no, uses heap-allocated queue |
| Code simplicity | simpler (4-line recursive function) | slightly more code (queue management) |
| Time complexity | O(rows * cols) | O(rows * cols) |
| Space complexity | O(rows * cols) worst case recursion depth | O(min(rows, cols)) queue size |
package com.bank.service;
public class DFSvsBFS {
// DFS: simpler code, risk of stack overflow on 1000x1000 grids
// BFS: slightly more code, safe for large grids
// Both visit each cell once => same O(rows * cols) time
public static void main(String[] args) {
System.out.println("DFS: 4-line recursive function, stack overflow risk");
System.out.println("BFS: queue-based, safe for large grids");
System.out.println("Both: O(rows * cols) time");
}
}
What are the edge cases?
Edge cases include an empty grid, a grid with all water (zero islands), a grid with all land (one island), and a grid with a single cell. Another edge case is a grid where every cell is a separate island, which happens when land cells are only connected diagonally (diagonal does not count).
package com.bank.service;
public class IslandEdgeCases {
public static void main(String[] args) {
NumberOfIslands solver = new NumberOfIslands();
// All water: 0 islands
char[][] allWater = {{'0', '0'}, {'0', '0'}};
System.out.println("All water: " + solver.numIslands(allWater));
// All land: 1 island
char[][] allLand = {{'1', '1'}, {'1', '1'}};
System.out.println("All land: " + solver.numIslands(allLand));
// Diagonal only: 2 islands (diagonal does not connect)
char[][] diagonal = {{'1', '0'}, {'0', '1'}};
System.out.println("Diagonal: " + solver.numIslands(diagonal));
// Single cell land: 1 island
char[][] single = {{'1'}};
System.out.println("Single: " + solver.numIslands(single));
}
}
All water: 0
All land: 1
Diagonal: 2
Single: 1
What are common mistakes?
The most common mistake is forgetting the bounds check, which causes an ArrayIndexOutOfBoundsException. Another mistake is not marking cells as visited before enqueueing in BFS, which leads to duplicate processing and potentially exceeding memory. A third mistake is counting diagonal neighbours, which the problem does not allow.
Wrong code that forgets bounds check:
// WRONG: no bounds check, throws ArrayIndexOutOfBoundsException
private void dfsBad(char[][] grid, int r, int c) {
if (grid[r][c] == '0') return; // crashes when r or c is out of bounds
grid[r][c] = '0';
dfsBad(grid, r + 1, c);
dfsBad(grid, r - 1, c);
dfsBad(grid, r, c + 1);
dfsBad(grid, r, c - 1);
}
Correct code with bounds check first:
// CORRECT: bounds check before accessing the array
private void dfsGood(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length
|| grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfsGood(grid, r + 1, c);
dfsGood(grid, r - 1, c);
dfsGood(grid, r, c + 1);
dfsGood(grid, r, c - 1);
}
Can you solve it with Union-Find?
Yes. Union-Find is an alternative that avoids recursion entirely. Initialise each land cell as its own set. Then scan the grid and union adjacent land cells. The number of distinct sets at the end is the number of islands. This approach is useful when the grid is built incrementally.
package com.bank.service;
public class NumberOfIslandsUnionFind {
private int[] parent;
private int[] rank;
private int count;
public int numIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
parent = new int[rows * cols];
rank = new int[rows * cols];
count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
int id = r * cols + c;
parent[id] = id;
count++;
}
}
}
int[][] directions = {{1, 0}, {0, 1}}; // only right and down to avoid double-union
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
for (int[] d : directions) {
int nr = r + d[0], nc = c + d[1];
if (nr < rows && nc < cols && grid[nr][nc] == '1') {
union(r * cols + c, nr * cols + nc);
}
}
}
}
}
return count;
}
private int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
private void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) parent[ra] = rb;
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }
count--;
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0'},
{'1', '0', '0', '1'},
{'0', '0', '1', '1'}
};
System.out.println("Islands (Union-Find): " + new NumberOfIslandsUnionFind().numIslands(grid));
}
}
Islands (Union-Find): 3
What should a senior engineer know?
A senior engineer chooses BFS over recursive DFS when the grid is very large to avoid stack overflow. They know that in-place marking mutates the input, so they copy the grid first if the caller needs it preserved. They also know that Union-Find is better when cells are added dynamically, because each new land cell can be unioned with its neighbours in near-constant time. In production at National Bank of India, the coverage map is large and updates arrive in real time, so Union-Find with path compression handles incremental island counting efficiently.
package com.bank.service;
public class SeniorIslandNotes {
// 1. BFS for large grids to avoid stack overflow
// 2. Copy grid before DFS/BFS if caller needs original preserved
// 3. Union-Find for dynamic/incremental island counting
// 4. Time: O(rows * cols) for all approaches
// 5. Space: O(rows * cols) for Union-Find parent array
public static void main(String[] args) {
System.out.println("Senior choices:");
System.out.println(" Small grid -> DFS (simplest)");
System.out.println(" Large grid -> BFS (safe stack)");
System.out.println(" Dynamic grid -> Union-Find (incremental)");
}
}
Senior choices:
Small grid -> DFS (simplest)
Large grid -> BFS (safe stack)
Dynamic grid -> Union-Find (incremental)
Visual Overview
Grid with 3 Islands
col 0 col 1 col 2 col 3 col 4
row 0 │ 1 │ 1 │ 0 │ 0 │ 0 │
row 1 │ 1 │ 1 │ 0 │ 0 │ 0 │
row 2 │ 0 │ 0 │ 1 │ 0 │ 0 │
row 3 │ 0 │ 0 │ 0 │ 1 │ 1 │
Island 1: (0,0)-(0,1)-(1,0)-(1,1) [top-left block]
Island 2: (2,2) [centre cell]
Island 3: (3,3)-(3,4) [bottom-right pair]
DFS Flood Fill from (0,0)
Step 1: visit (0,0), mark '0', recurse down
Step 2: visit (1,0), mark '0', recurse right
Step 3: visit (1,1), mark '0', recurse up
Step 4: visit (0,1), mark '0', all neighbours visited
Result: entire Island 1 marked as water
After flood fill of Island 1:
col 0 col 1 col 2 col 3 col 4
row 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
row 1 │ 0 │ 0 │ 0 │ 0 │ 0 │
row 2 │ 0 │ 0 │ 1 │ 0 │ 0 │
row 3 │ 0 │ 0 │ 0 │ 1 │ 1 │
Key Takeaway
Number of Islands is a connected-components counting problem on a grid. The approach is to sweep every cell, and whenever an unvisited land cell is found, increment the island count and launch a flood fill that marks the entire connected component as visited so it is never counted again. Each cell is touched at most a constant number of times, so the total time is O(rows times cols).
The flood fill can be DFS or BFS. DFS is simpler to code as a four-line recursive function that marks the current cell and recurses into its four neighbours with bounds and water checks. BFS uses a queue and avoids the risk of stack overflow on very large grids. Both produce the same result in the same time complexity.
The senior-level considerations are choosing BFS for large grids, copying the grid before modification if the caller needs it preserved, and using Union-Find when cells are added dynamically. At the National Bank of India, the branch coverage map is large and updates arrive in real time as new branches open, so Union-Find with path compression handles incremental island counting without rebuilding the entire grid.
The most common mistakes are forgetting the bounds check before accessing the array, not marking cells before enqueueing in BFS which leads to duplicate processing, and counting diagonal neighbours which the problem does not allow. The bounds check must come before the array access to avoid an ArrayIndexOutOfBoundsException.
Remember one sentence: sweep the grid, count one island per unvisited land cell, and flood-fill each connected component as visited so no island is counted twice.
---