200. Number of Islands

Number of Islands is the problem that makes connected-components click. The grid looks like a matrix problem, but it’s really a graph traversal in disguise — every land cell is a node, and neighbors that touch are edges. Once you see that, the count is just “how many times did I have to start a fresh search?”

The problem

You’re handed a grid of '1' (land) and '0' (water). An island is a blob of land cells joined up, down, left, or right, and you return how many separate islands there are. (Full statement on LeetCode.)

1 1 0 0
1 1 0 0
0 0 1 0   ->  3 islands
0 0 0 1

The top-left 1s form one island, the lone 1 in row 3 is another, and the 1 in row 4 is the third.

Intuition: sink each island the moment you find it

Scan the grid cell by cell. Most cells are water or land you’ve already accounted for — skip those. But the moment you hit a '1' you haven’t visited, you know you’re standing on a brand-new island, so you bump the count by one.

The trick is what happens next: before moving on, you flood the whole island. From that starting cell you walk to every connected land cell and flip it to water. That erasure is what stops you from counting the same island again — by the time the outer scan reaches the rest of this blob, it’s all '0'. So the number of islands equals the number of times the scan had to kick off a fresh flood.

Marking cells as visited by overwriting them with '0' costs no extra memory. A cell can be looked at several times — a flood peeks at it from each adjacent cell — but each land cell is sunk (processed) exactly once, and every look is $O(1)$, so the total stays $O(mn)$.

Solution

A flood fill does the counting. Each unvisited '1' kicks off a flood that sinks its whole island with an explicit stack — a recursive DFS reads a hair cleaner, but a solid 300×300 island can nest ~90,000 calls and overflow Java’s default stack, so the iterative version is the safe default.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    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') {  // start of an unvisited island
                    sink(grid, r, c);     // flood it so it's counted once
                    count++;
                }
            }
        }
        return count;
    }

    // Flip this land cell and every connected one to water, iteratively.
    private void sink(char[][] grid, int sr, int sc) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> stack = new ArrayDeque<>();
        grid[sr][sc] = '0';           // mark on push so a cell is never queued twice
        stack.push(new int[] {sr, sc});
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            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') continue;   // water or already sunk
                grid[nr][nc] = '0';
                stack.push(new int[] {nr, nc});
            }
        }
    }
}

Sinking a cell (grid[nr][nc] = '0') at the moment you push it, not when you pop it, is what keeps a cell from being queued twice and stops neighbors bouncing back into land you’ve already claimed.

Complexity

	Time	Space
DFS flood fill	$O(mn)$	$O(mn)$

Time is one visit per cell across the scan and floods. The space is the explicit stack: in the worst case — one solid island filling the grid — it can hold up to $O(mn)$ cells at once. Moving that frontier off the call stack onto the heap is what avoids StackOverflowError (the JVM caps call depth far below available heap); the $O(mn)$ worst-case auxiliary space is the same either way.

In an interview

Say the reframe out loud first: “this is counting connected components, so I’ll scan for an unvisited land cell, flood-fill its island, and count each flood.” That one sentence signals you recognized the graph underneath the grid, which is the real thing being tested.

The detail worth naming is depth. A recursive flood is the first thing most people write, but with the grid up to 300×300 a single giant island means ~90,000 nested calls, which can overflow the call stack — which is why the solution above keeps the frontier on an explicit stack instead. Say that out loud even if you write the recursion first; it’s the kind of robustness interviewers like to hear. Also mention whether mutating the input is allowed; if not, use a separate boolean[][] visited instead of overwriting cells.

This flood-fill-and-count shape is the backbone of the graph patterns hub. The closest sibling is Number of Connected Components in an Undirected Graph, which is the same “count the searches” idea on an explicit edge list, and Pacific Atlantic Water Flow reuses grid DFS but flips the direction — flooding inward from the borders instead.

References

• LeetCode 200 — Number of Islands