Count the Number of Islands (Grid DFS Flood Fill)

• Number of Islands treats a grid as an implicit graph where each land cell is a node connected to its four orthogonal land neighbors.
• Flood fill (DFS or BFS) from each unvisited land cell marks the entire connected region as visited.
• Island count equals the number of flood fills started, because each fill covers one complete island.
• In-place marking overwrites visited land with water to avoid a separate visited array.
• Time is O(rows * cols) visiting each cell a bounded number of times.
• Space is O(rows * cols) worst case for the recursion stack on a single large island.

What is the Number of Islands problem?

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is a group of land cells connected horizontally or vertically (not diagonally). This is the canonical connected-components problem on a grid, solved by flood fill.

package com.bank.service;

public class FraudRingCounter {
    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++;
                    floodFill(grid, r, c, rows, cols);
                }
            }
        }
        return count;
    }

    private void floodFill(char[][] grid, int r, int c,
                            int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || grid[r][c] != '1') {
            return;
        }
        grid[r][c] = '0';  // mark visited by sinking the land
        floodFill(grid, r - 1, c, rows, cols);
        floodFill(grid, r + 1, c, rows, cols);
        floodFill(grid, r, c - 1, rows, cols);
        floodFill(grid, r, c + 1, rows, cols);
    }
}

Why does each flood fill correspond to exactly one island?

When the outer loop finds an unvisited land cell, it starts a flood fill that reaches and marks every land cell connected to it. By the time the fill finishes, the entire island is marked as water. Any land the outer loop later encounters must belong to a different island, because it was not reachable from the previous start.

Grid:   1 1 0 0 0
        1 1 0 0 0
        0 0 1 0 0
        0 0 0 1 1

Flood fill from (0,0): marks {(0,0),(0,1),(1,0),(1,1)} → island 1
Flood fill from (2,2): marks {(2,2)} → island 2
Flood fill from (3,3): marks {(3,3),(3,4)} → island 3
Result: 3 islands

How does the in-place marking trick work?

Instead of maintaining a separate boolean visited array, you overwrite each visited land cell with '0' (water). This serves as the visited marker because the flood fill only processes cells that are '1'. The grid is modified in place, which is acceptable if the original grid is not needed afterward.

// In-place marking: no extra visited array needed
grid[r][c] = '0';  // visited land becomes water

// Alternative: separate visited array
boolean[][] visited = new boolean[rows][cols];
if (!visited[r][c] && grid[r][c] == '1') {
    visited[r][c] = true;
    // ... recurse
}

What is the iterative BFS alternative?

For very large grids where a single island might span most of the grid, the recursive DFS can overflow the call stack. The iterative BFS version uses a queue and has the same logic but avoids deep recursion.

private void floodFillBFS(char[][] grid, int r, int c,
                           int rows, int cols) {
    java.util.Queue<int[]> queue = new java.util.LinkedList<>();
    queue.offer(new int[]{r, c});
    grid[r][c] = '0';
    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 < rows && nc >= 0 && nc < cols
                    && grid[nr][nc] == '1') {
                grid[nr][nc] = '0';
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

How is this related to Union-Find?

The Union-Find approach treats each land cell as a set element and unions adjacent land cells. Both approaches give the same island count. The DFS approach is simpler for a static grid; Union-Find shines when land is added incrementally.

| Aspect | DFS Flood Fill | Union-Find |
|--------|---------------|------------|
| Simplicity | Simpler | More complex |
| Dynamic additions | Must re-scan | O(alpha) per addition |
| Stack overflow risk | Yes for huge islands | No |
| Space | O(1) with in-place, O(R*C) stack | O(R*C) for parent/rank |

What are edge cases?

• Empty grid: return 0.
• All water: return 0.
• All land: return 1 (one giant island).
• Single cell '1': return 1.
• Grid with only diagonal connections: those are separate islands because only horizontal and vertical connections count.

// Edge case: diagonal connections do NOT form an island
// Grid: 1 0
//        0 1
// Result: 2 islands (not connected diagonally)

What are common mistakes?

The first mistake is marking cells at dequeue time instead of enqueue time in BFS, which causes cells to be enqueued multiple times. The second mistake is checking diagonal neighbors, which the problem does not count. The third mistake is not handling the out-of-bounds check before accessing the grid.

// WRONG: mark at dequeue time
int[] cell = queue.poll();
grid[cell[0]][cell[1]] = '0';  // too late, may already be enqueued

// CORRECT: mark at enqueue time
grid[nr][nc] = '0';  // mark before enqueueing
queue.offer(new int[]{nr, nc});

What should a senior engineer know?

The recursive DFS can reach a call stack depth equal to the number of cells in the largest island. For a 1000x1000 grid that is entirely land, that is 1,000,000 recursive calls, which will overflow the default Java stack. Production code should use the iterative BFS or an explicit stack. The same pattern applies to flood-fill paint tools, region labeling in image processing, and connected-component analysis.

At the National Bank of India, Rajesh used this in fraud analytics where suspicious accounts plotted on a spatial grid formed clusters. Counting distinct rings let the team size its investigation effort, and the flood fill guaranteed each ring was counted exactly once.