Number of Islands

mediumTests passed 2026-11-11v1.0.0
TC: O(M * N)|SC: O(M * N)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Iterate every cell `(r, c)`. Whenever `grid[r][c] == "1"`, increment `islands` and immediately flood-fill (DFS/BFS) all 4-connected `"1"` cells to `"0"` in-place so each component is counted once.

2. Complexity Bounds & Proof

Each cell is marked visited at most once; worst-case DFS recursion/BFS queue holds all M*N cells.

3. Minimal Idiomatic Code

def numIslands(grid: list[list[str]]) -> int:
    R, C = len(grid), len(grid[0])
    ans = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                ans += 1
                grid[r][c] = '0'
                q = deque([(r, c)])
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            q.append((nr, nc))
    return ans

4. Failure Modes & Interview Follow-ups

Pitfalls:- Marking visited upon *popping* from BFS queue instead of before *pushing* causes exponential duplicate enqueues. - Using BFS uses O(min(M, N)) queue memory vs O(M*N) call stack in worst-case spiral DFS.
Follow-ups:- Dynamic islands added online: use Union-Find on `(r * cols + c)` grid indices.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Max Area of Island (O(M * N))Rotting Oranges (O(M * N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.