Number of Islands II — Online Queries with Union-Find (LC 305)

Problem Statement#

LeetCode 305 — Number of Islands II (Hard)

You are given an empty m x n 2D grid that initially has all water. You will be given a list of positions where you need to add land. Each addition turns the cell at the given position into land. Your task is to return an array of integers, where each integer represents the number of islands after each addition.

Constraints:

• 1 <= m, n <= 10^4
• 1 <= positions.length <= 10^4
• Coordinates are within bounds.

Example:

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output: [1, 1, 2, 3]
Explanation:
After [0,0]: one island.
After [0,1]: still one island (merges with previous).
After [1,2]: two islands ((0,0)-(0,1) and (1,2)).
After [2,1]: three islands (all separate).

Why This Problem Matters#

Number of Islands II is the flagship online connectivity problem at FAANG companies. The naive approach — re-run BFS after every addition — is O(k times m times n), which is far too slow. The correct solution uses Union-Find (Disjoint Set Union) with path compression and union by rank, achieving nearly O(alpha(n)) per operation, where alpha is the inverse Ackermann function (effectively constant).

This problem teaches you to think about dynamic connectivity — a topic that shows up in network reliability, social graph clustering, and percolation simulation. Once you understand the DSU pattern here, you can solve LC 1101 (smallest common ancestor over time), LC 803 (bricks falling), and LC 1135 (minimum spanning tree connections). Google in particular uses this problem as a Hard-tier evaluation in senior interview loops.

The Core Insight#

For each new land addition (r, c):

1. Convert (r, c) into a 1D index: idx = r * n + c. Make it its own component, increment the island count.
2. For each of the 4 neighbors:
   • If the neighbor is also land and belongs to a different component, union them and decrement the island count.
   • If they are already in the same component, do nothing.
3. After processing all 4 neighbors, append the current count to the result.

The key invariants:

• Adding a new cell always increments by 1 first.
• Each successful union decrements by 1 (since two components merge into one).
• Skip already-land positions to handle duplicate inputs (LeetCode test cases include them).

Why DSU and not BFS? Each addition only affects a constant number of neighbors. DSU's amortized near-O(1) find and union make the total work O(k times alpha(N)) for k operations on N cells. BFS would re-explore the entire grid from scratch.

Visual Dry Run#

m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]].

Solution (Optimal)#

Python#

class Solution:
    def numIslands2(self, m: int, n: int, positions: list[list[int]]) -> list[int]:
        parent = [-1] * (m * n)                  # -1 means water (unset)
        rank = [0] * (m * n)
        count = 0
        result = []
 
        def find(x: int) -> int:
            # iterative find with path compression
            root = x
            while parent[root] != root:
                root = parent[root]
            while parent[x] != root:
                parent[x], x = root, parent[x]
            return root
 
        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                     # already connected, no merge
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra                  # attach smaller under larger
            parent[rb] = ra
            if rank[ra] == rank[rb]:
                rank[ra] += 1
            return True
 
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
        for r, c in positions:
            idx = r * n + c
            if parent[idx] != -1:                # already land (duplicate)
                result.append(count)
                continue
            parent[idx] = idx                    # initialize as own root
            count += 1
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                nidx = nr * n + nc
                if 0 <= nr < m and 0 <= nc < n and parent[nidx] != -1:
                    if union(idx, nidx):
                        count -= 1               # merge reduces island count
            result.append(count)
        return result

JavaScript#

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} positions
 * @return {number[]}
 */
var numIslands2 = function(m, n, positions) {
    const parent = new Array(m * n).fill(-1);
    const rank = new Array(m * n).fill(0);
    let count = 0;
    const result = [];
 
    function find(x) {
        let root = x;
        while (parent[root] !== root) root = parent[root];
        while (parent[x] !== root) { const nxt = parent[x]; parent[x] = root; x = nxt; }
        return root;
    }
 
    function union(a, b) {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;
        if (rank[ra] < rank[rb]) { parent[ra] = rb; }
        else if (rank[ra] > rank[rb]) { parent[rb] = ra; }
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
 
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
 
    for (const [r, c] of positions) {
        const idx = r * n + c;
        if (parent[idx] !== -1) { result.push(count); continue; }
        parent[idx] = idx;
        count++;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            const nidx = nr * n + nc;
            if (parent[nidx] === -1) continue;   // neighbor is water
            if (union(idx, nidx)) count--;
        }
        result.push(count);
    }
    return result;
};

Time Complexity: O(k times alpha(m times n)) where k is the number of positions. Space Complexity: O(m times n) for the parent and rank arrays.

Common Mistakes#

1. Not handling duplicate positions. LeetCode's test cases include duplicates — adding the same cell twice should not change the count.
2. Skipping union by rank or path compression. Without these, find degrades to O(log n) worst case and O(n) average — risky on tight time limits.
3. Initializing parent to range(m*n) instead of -1. This makes every cell look like land from the start, breaking the "is it water?" check.
4. Decrementing count on every neighbor visit. You must only decrement when union returns true (an actual merge happened). Two neighbors may already share a component.
5. Using BFS to recount islands after each addition. Times out on larger inputs.

Interview Tips#

• Open with the constraint. "k operations on a m times n grid — re-running BFS is too expensive. Union-Find with path compression and rank gives near-O(1) per query."
• State the alpha bound. Knowing alpha(N) is effectively constant signals algorithm-class fluency.
• Walk through duplicates. Mention them explicitly so the interviewer knows you considered the edge case.
• Mention 1D index trick. r * n + c flattens 2D to 1D for the parent array — clean and avoids hash lookups.

Follow-up Questions#

1. What if cells are also removed (turn back to water)? DSU does not support easy deletions. Use offline reverse-time processing: do additions in reverse and treat removals as initial state.
2. What if you also need the largest island size? Track size[root] in DSU and update on union; query size[find(idx)] for size lookups.
3. What if the grid is sparse and m, n are very large but most cells stay water? Use a hash map for parent instead of a flat array to avoid allocating m*n slots.
4. Diagonals count? Expand the directions array; everything else is identical.

Key Takeaways#

• Number of Islands II is solved with Union-Find (DSU) with path compression and union by rank.
• Increment count when you add a new cell; decrement once per successful union.
• Always handle duplicate positions to match LeetCode's test cases.
• Initialize parent to -1 to distinguish water from land — do not use range(m*n).
• Time is O(k times alpha(m times n)), effectively linear in the number of operations.
• DSU is the right hammer whenever you have online connectivity queries; remember this template.