A coastal map service counts land masses on a binary raster: '1' is land, '0' is water. The intern nested a neighbor walk from every land cell and never marked a cell. An 8×8 fixture in staging hung: two adjacent '1's bounced forever. They added a local seen set but still restarted a full flood from every land cell. Staging returned in milliseconds. A million-cell continent in production was still flooding when the request timed out.

Number of Islands asks how many 4-connected land blobs sit in the grid. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the DFS post owns the walk. Here we only care about four neighbor deltas, marking land we have already flooded, and counting how many times we start.

The problem

Given a char[][] grid of '1' (land) and '0' (water), return how many islands it holds. Two land cells are the same island when you can walk four directions — up, down, left, right — not diagonals. You may mutate the grid.

1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0     →  1

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

0 0
0 0           →  0

Note: Off-board is water. Bounds-check first, then skip '0'. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them.

Restarting a flood from every land cell is the honest brute force

A neighbor walk with no mark never returns. From a '1', step to a neighbor '1', step back, repeat. Staging’s hang was that bounce.

The honest version marks inside one flood so the walk terminates, throws the marks away, and starts again from the next land cell — a set of those cell-sets collapses duplicates. Correct. Quadratic.

int numIslandsRestart(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Set<Set<Integer>> islands = new HashSet<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                Set<Integer> cells = new HashSet<>();
                collect(grid, r, c, dirs, cells);
                islands.add(cells);
            }
        }
    }
    return islands.size();
}

void collect(char[][] grid, int r, int c, int[][] dirs, Set<Integer> cells) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
        return;
    }
    if (grid[r][c] != '1' || !cells.add(r * grid[0].length + c)) {
        return;
    }
    for (int[] d : dirs) {
        collect(grid, r + d[0], c + d[1], dirs, cells);
    }
}

At an 8×8 fixture this is a rounding error. On one island of V land cells you restart a V-cell flood V times: you paid a full walk per land cell for a question that only needs one walk per island.

Count starts, then sink the component

Scan row-major. Every time the cell is still '1', that cell is a new island: increment, then flood. The flood writes '1' → '0' so a later scan cannot start the same blob again.

1 1 0
1 0 1

scan (0,0) land   islands=1
  flood sinks (0,0), (0,1), (1,0)
scan (0,1) already '0'
scan (0,2) water
scan (1,0) already '0'
scan (1,1) water
scan (1,2) land   islands=2
  flood sinks (1,2)

Four deltas, bounds-check, skip water. Mutation is allowed, so skip a second boolean[][]. The Java is that walk; the guard is bounds plus “not land.”

int numIslands(char[][] grid) {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int islands = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                islands++;
                flood(grid, r, c, dirs);
            }
        }
    }
    return islands;
}

void flood(char[][] grid, int r, int c, int[][] dirs) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
        return;
    }
    grid[r][c] = '0';
    for (int[] d : dirs) {
        flood(grid, r + d[0], c + d[1], dirs);
    }
}

Time is O(mn) — each cell is sunk at most once, and each sunk cell looks at four neighbors. Space is O(mn) for the call stack on a solid island. A million-cell island is a million frames; an iterative ArrayDeque is the same bound without blowing the JVM stack.

Note: Increment, then flood. Flood first and forget the increment, and the island vanishes uncounted. Increment and forget to sink, and every remaining '1' of the same blob is another start.

What interviewers usually poke next

  • Iterative flood. Same sink, an ArrayDeque of cells. BFS (offer / poll) or explicit DFS (push / pop). Not java.util.Stack. Not ArrayList.remove(0).
  • Max Area of Island. Count cells inside the flood, keep the max. Same walk, different return.
  • Number of Provinces. Cities and an n × n connection matrix, not a raster. Same idea: count starts, mark the component.
  • Read-only grid, or diagonals. If mutation is forbidden, a boolean[][] seen is the mark. Diagonals are eight deltas — ask before you edit the table.

You are done with this problem when you can say, out loud, why an unmarked neighbor walk never returns, why restarting a flood from every land cell is quadratic, and why sinking (or a persistent seen) lets you count starts in one pass.