LeetCode 200 · Medium · Graphs

Number of Islands

Given an m × n grid of '1' (land) and '0' (water), return the number of islands: groups of land connected up, down, left or right.

O(m·n)time
O(m·n)space
1 DFSper island

rows of 0/1 separated by ; or new lines · 1–8 rows × 1–10 columns · or tap cells below

grid tap a cell to toggle land / water · the run restarts

landwatervisitedframe openprobed, rejectedscan

Call stack dfs frames, bottom → top · grey arrow = tried, red = waiting on it

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private char[][] grid;private boolean[][] visit;private int rows;private int cols;public int numIslands(char[][] grid) { this.grid = grid; rows = grid.length; cols = grid[0].length; visit = new boolean[rows][cols]; int islands = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == '1' && !visit[r][c]) { islands++; dfs(r, c); } } } return islands;}private void dfs(int r, int c) { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' || visit[r][c]) { return; } visit[r][c] = true; // mark on entry for (int[] d : DIRS) { dfs(r + d[0], c + d[1]); }}
    scan (r, c)
    —
    islands
    0
    dfs frame
    —
    depth
    0
    visited cells
    0

    Why it works

    1. Brute force would search from every 1 and then de-duplicate the islands it found: O((m·n)²). A shared visit array means each cell is explored once.
    2. Invariant: when the scan meets a 1 that is not in visit, it is a new island. The DFS of every earlier island painted all of its cells before the scan moved on.
    3. O(m·n) time: each cell is entered at most once and probes 4 neighbours. O(m·n) space for visit and, for a snake-shaped island, the recursion stack.
    4. Pitfall: mark on entry, not on exit. Adding to visit after the loop lets two neighbours call each other forever. And only 4 directions count: a checkerboard is all single-cell islands.
    5. Variants: sink cells in place (grid[r][c] = '0') to drop the visit array; BFS with an ArrayDeque avoids a StackOverflowError on huge grids; union-find handles land added one cell at a time (Number of Islands II).