Number of Islands

1. Problem & Core Objective

Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is land connected horizontally or vertically, and the grid is surrounded by water.

1 1 0 0 0
1 1 0 0 0        →  3
0 0 1 0 0
0 0 0 1 1

Constraints: 1 <= m, n <= 300 · cells are '0' or '1'

What's actually being tested: recognising a grid as an implicit graph and counting connected components. The whole section rests on this — seven of thirteen questions are grid traversals, and this is the simplest.

2. First-Principles Thought Process

The grid is already a graph

You never build an adjacency list. Each cell is a node; its neighbours are the four cells around it, computed arithmetically.

With V = m · n cells and E ≤ 4V edges, O(V + E) is simply O(m · n).

Counting components

An island is a connected component of land cells. The standard algorithm for counting components:

for each cell:
    if it is unvisited land:
        count++
        flood the entire component so it is never counted again

The traversal doesn't need to find anything — it exists purely to mark the component so its other cells don't trigger a second count.

Why every cell is visited at most twice

The outer loop touches each cell once. The flood marks each land cell once, and a marked cell is never re-entered. So the total is O(m · n) regardless of how the land is arranged — the flood's cost across all calls sums to the number of land cells, not the number of calls times the grid size.

That amortised argument is worth being able to state: it's why "a DFS inside a double loop" isn't O((m·n)²).

DFS or BFS?

Either works — this is reachability, not shortest path, so the traversal order is irrelevant.

The real trade is stack depth. DFS recursion on a 300 × 300 grid of all land is 90,000 frames deep, which overflows the default JVM stack. BFS uses an explicit queue on the heap and is bounded by the frontier width.

At these constraints DFS genuinely can overflow, so it's worth raising rather than defaulting.

3. Solution Paths

Approach 1 — DFS flood fill

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == '1') { count++; sink(grid, r, c); }
    return count;
}

private void sink(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';                                  // mark visited by sinking it
    for (int[] d : DIRS) sink(g, r + d[0], c + d[1]);
}

• Time O(m · n) · Space O(m · n) worst-case recursion depth

Counter-questions on this approach

⭐ "A DFS inside a double loop — isn't that O((m·n)²)?"

No, and the reason is amortisation. The sink is only called on an unvisited land cell, and it immediately marks everything it reaches. So across the entire run, each land cell is sunk exactly once.

The outer loop is O(m · n) and the total flood work is also O(m · n) — they add rather than multiply. The loop finds components; the flood consumes them.

⭐ "You overwrite the caller's grid. Is that acceptable?"

It destroys the input — every island becomes water. That's fine if the caller doesn't need it, but it's a real side effect and I'd flag it.

The alternative is a separate boolean[][] visited, which costs O(m · n) space but leaves the grid intact. At 300 × 300 that's 90,000 booleans — trivial. I'd usually prefer it for the cleanliness unless told memory is tight.

⭐ "What's the actual stack depth risk?"

A 300 × 300 grid of all '1' is a single island of 90,000 cells, and the DFS can recurse that deep in a snake-like path. Java's default thread stack is around 512 KB, which typically handles a few thousand frames — 90,000 will overflow.

So at these exact constraints this can fail. That's the argument for BFS, or for an explicit stack.

"Why check bounds inside sink rather than before calling it?"

It keeps the four recursive calls uniform — no guard duplicated per direction. The cost is one extra call per out-of-bounds neighbour, which is negligible. Checking before would mean four bounds tests at the call site instead of one at the top.

Approach 2 — BFS flood fill (safer at these sizes)

public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length, count = 0;
    boolean[][] visited = new boolean[m][n];

    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != '1' || visited[r][c]) continue;
            count++;

            Queue<int[]> q = new ArrayDeque<>();
            q.offer(new int[]{r, c});
            visited[r][c] = true;                    // mark on ENQUEUE, not on dequeue

            while (!q.isEmpty()) {
                int[] cell = q.poll();
                for (int[] d : DIRS) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (grid[nr][nc] != '1' || visited[nr][nc]) continue;
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
    return count;
}

• Time O(m · n) · Space O(min(m, n)) queue, plus O(m · n) for visited

Counter-questions on this approach

⭐ "Why mark visited on enqueue rather than on dequeue?"

Because a cell can be reached from several neighbours before it's processed. Marking on dequeue lets it be enqueued multiple times — the answer stays correct, but the queue can grow to O(m · n) with duplicates and the work multiplies.

Marking on enqueue guarantees each cell enters the queue exactly once. It's the standard BFS discipline and it matters more here than the correctness of the count suggests.

⭐ "Why is the queue O(min(m, n)) and not O(m · n)?"

Because BFS holds a frontier, not the whole component. On a grid the frontier is roughly a diagonal wavefront, bounded by the shorter dimension.

The worst case is a bit larger than that in practice, but the point stands: the queue is far smaller than the component, unlike DFS's stack which can equal it.

"So BFS is strictly better here?"

On stack safety, yes. It costs the visited array — though DFS needs that too unless it mutates the grid. And it's more code.

I'd write DFS if the grid were small and mutation acceptable, and BFS at these constraints because 90,000 frames is a genuine overflow risk.

Approach 3 — Union-Find

public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    DSU dsu = new DSU(m * n);
    int land = 0;

    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != '1') continue;
            land++;
            if (r > 0 && grid[r-1][c] == '1') dsu.union(r*n + c, (r-1)*n + c);
            if (c > 0 && grid[r][c-1] == '1') dsu.union(r*n + c, r*n + c - 1);
        }
    return land - dsu.merges;      // each successful union removes one component
}

• Time O(m · n · α) · Space O(m · n)

Counter-questions on this approach

⭐ "Same complexity, more code. When is this the right choice?"

When the grid changes. If islands are added one cell at a time and you need the count after each addition — that's LeetCode 305, Number of Islands II — union-find handles it incrementally at O(α) per addition. A flood fill would rerun the whole traversal each time.

For a static grid it's over-built, and I'd say so rather than presenting it as an improvement.

"Why only check up and left, not all four directions?"

Because the scan is in row-major order, so when I reach a cell its up and left neighbours are already processed. Checking down and right would just perform each union twice — harmless but wasteful.

That's a small but real economy: half the union calls.

"Why land - merges rather than counting distinct roots?"

Both work. Each successful union reduces the component count by exactly one, so tracking merges avoids a final O(m·n) pass calling find on every land cell. Counting roots is more obviously correct; counting merges is cheaper.

Comparison

4. Why the Optimal Wins

All three are linear in the grid size — you must look at every cell at least once, so that's the floor.

BFS wins here for a practical reason rather than an asymptotic one: at 300 × 300 the DFS recursion can reach 90,000 frames on an all-land grid and overflow. That's not a theoretical concern at these exact constraints.

Union-find matches on complexity but earns its keep only when the grid is dynamic — and saying that clearly is better than presenting it as a general improvement.

The framing worth keeping:

A grid is a graph with four implicit edges per node. Counting islands is counting connected components: iterate every cell, and when you find an unvisited one, flood its whole component so it is never counted again.

5. Java Prerequisites

Direction array — the standard grid idiom:

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; ... }

Bounds check before indexing

if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

Order matters — grid[nr][nc] after an out-of-range nr throws.

Flattening 2-D coordinates — for union-find or a 1-D visited array:

int id = r * n + c;        // n is the number of COLUMNS
int r = id / n, c = id % n;

Divide by the column count — the same trap as Search a 2D Matrix.

ArrayDeque for the queue — faster than LinkedList, forbids nulls.

6. Interview Communication Guide

Clarifying questions: Are diagonals connected (no — four directions)? May I modify the grid (it decides sink-vs-visited)? Is the grid guaranteed non-empty (yes, m, n >= 1)? How large can it get (300 × 300 — enough to overflow a DFS)?

The pitch

"The grid is already a graph — each cell is a node and its four neighbours are its edges, computed arithmetically, so I never build an adjacency list. With V = m·n and E ≤ 4V, any traversal is O(m·n).

An island is a connected component of land, so this is component counting: scan every cell, and when I find unvisited land, increment the count and flood the entire component so its other cells never trigger a second count.

The flood isn't searching for anything — it exists purely to mark.

Worth addressing: a DFS inside a double loop looks quadratic but isn't. The flood only runs on unvisited land and marks everything it touches, so each cell is flooded exactly once across the whole run. The loop and the flood add rather than multiply — O(m·n) total.

On DFS versus BFS: either is correct since this is reachability, not shortest path. But at 300 × 300, a grid of all land is one island of 90,000 cells, and the DFS can recurse that deep — which overflows Java's default stack. So I'd use BFS with an explicit queue.

One BFS detail: mark visited on enqueue, not dequeue. A cell reachable from several neighbours would otherwise be queued multiple times before processing.

I'd also use a separate visited array rather than sinking cells to '0', so the caller's grid survives — 90,000 booleans is nothing."

Edge cases to volunteer:

Name the all-land grid and the diagonal case. The first is where DFS overflows; the second catches anyone who included diagonal neighbours.

7. Follow-Up Questions — Modified Constraints

⭐ "The grid changes — land is added one cell at a time, report the count after each addition."

LeetCode 305. Union-find is the right structure: each new land cell starts as its own component, then unions with any adjacent land, and each successful union decrements the count. O(α) per addition versus re-flooding the whole grid.

This is the case where union-find stops being over-built.

⭐ "Count diagonal connections as well."

Extend DIRS to eight offsets. Nothing else changes — which is a good sign the neighbour function is properly factored out of the traversal.

"Return the size of the largest island."

Question 2 in this section. The flood returns a count instead of nothing, and the outer loop keeps a maximum.

"What if the grid were 10^5 × 10^5, too large for memory?"

You'd stream it row by row and use union-find over just two rows at a time, merging components as rows scroll past. That's the standard connected-component labelling algorithm for large images, and it's O(m·n) time with O(n) memory.

"Count the islands' perimeter as well."

Each land cell contributes 4 minus its number of land neighbours. Computed during the same flood — O(m·n) with no extra pass.

"What if the grid were a torus — edges wrap around?"

The bounds check becomes a modulo: nr = (r + d[0] + m) % m. The + m handles negative indices, since Java's % keeps the sign of the dividend. Everything else is unchanged.