Amazon — Number of Islands II (Dynamic Union-Find)

Problem Statement#

You are given an m x n grid initially filled with water. Process a sequence of addLand(r, c) operations that turn water cells into land. After each operation, return the current number of distinct islands.

Constraints:

• 1 <= m, n <= 3 * 10^4
• 1 <= positions.length <= 3 * 10^4
• 0 <= r < m, 0 <= c < n

Input:  m=3, n=3, positions=[[0,0],[0,1],[1,2],[1,1]]
Output: [1,1,2,1]

Input:  m=1, n=1, positions=[[0,0]]
Output: [1]

Why This Problem Matters#

Number of Islands II (LeetCode 305) is an Amazon flagship interview problem that tests understanding of dynamic graph connectivity — a skill directly relevant to Amazon's distributed systems, where services and nodes join and leave clusters dynamically. Understanding when two components merge is exactly what Amazon's internal service mesh must do in real-time.

The naive approach re-runs BFS/DFS after every addLand call, costing O(k * m * n) total time, which is too slow for large grids. The optimal solution uses Union-Find with path compression and union by rank, achieving nearly O(1) per operation amortized. This is the data structure Amazon expects senior engineers to know cold.

Google and Microsoft also ask this in the context of dynamic connectivity: "Given a stream of edge additions in a graph, track connected components." Number of Islands II is the grid-specific instance of that general problem.

The Core Insight#

Maintain a Union-Find (Disjoint Set Union) structure over the grid cells. When addLand(r, c) is called:

1. If already land, skip (return current count)
2. Create a new component for this cell — increment island count by 1
3. Check all 4 neighbors — if any neighbor is land, union the two components
4. Each successful union (merging two different components) decrements island count by 1

The island count starts at 0 and is adjusted by +1 for new land and -1 for each merge. After all 4 neighbors are processed, append the current count.

Visual Dry Run#

3x3 grid, positions: (0,0), (0,1), (1,2), (1,1)

Solution (Optimal)#

class Solution:
    def numIslands2(self, m: int, n: int, positions: list) -> list:
        parent = {}
        rank = {}
        count = 0
 
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
 
        def union(x, y):
            nonlocal count
            px, py = find(x), find(y)
            if px == py:
                return
            if rank.get(px, 0) < rank.get(py, 0):
                px, py = py, px
            parent[py] = px
            if rank.get(px, 0) == rank.get(py, 0):
                rank[px] = rank.get(px, 0) + 1
            count -= 1
 
        res = []
        for r, c in positions:
            if (r, c) in parent:
                res.append(count)
                continue
            parent[(r, c)] = (r, c)
            rank[(r, c)] = 0
            count += 1
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if (nr, nc) in parent:
                    union((r, c), (nr, nc))
            res.append(count)
        return res

var numIslands2 = function(m, n, positions) {
    const parent = new Map();
    const rank = new Map();
    let count = 0;
 
    const find = (x) => {
        if (parent.get(x) !== x) parent.set(x, find(parent.get(x)));
        return parent.get(x);
    };
 
    const union = (x, y) => {
        const px = find(x), py = find(y);
        if (px === py) return;
        const rx = rank.get(px) || 0, ry = rank.get(py) || 0;
        if (rx < ry) { parent.set(px, py); }
        else if (rx > ry) { parent.set(py, px); }
        else { parent.set(py, px); rank.set(px, rx + 1); }
        count--;
    };
 
    const res = [];
    for (const [r, c] of positions) {
        const key = `${r},${c}`;
        if (!parent.has(key)) {
            parent.set(key, key);
            rank.set(key, 0);
            count++;
        }
        for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nk = `${r+dr},${c+dc}`;
            if (parent.has(nk)) union(key, nk);
        }
        res.push(count);
    }
    return res;
};

Time: O(k * alpha(mn)) ≈ O(k) — k is number of operations, alpha is inverse Ackermann (effectively constant) Space: O(mn) — Union-Find stores at most m*n entries

Common Mistakes#

• Re-running BFS/DFS from scratch after every operation — O(k * m * n) is too slow
• Forgetting to handle duplicate positions (same cell added twice)
• Not checking grid bounds when examining 4 neighbors
• Using 2D coordinates directly without hashing — causes key collisions in some languages
• Forgetting to decrement count for each merge (not just once per addLand)

Interview Tips#

• Start by explaining why BFS per operation is too slow — sets up the Union-Find motivation
• Implement find with path compression and union with union by rank — Amazon expects both
• Use a hash map instead of a fixed array when grid is large (avoid m*n initialization cost)
• Mention that duplicate positions must be handled — return current count unchanged
• Discuss the inverse Ackermann function briefly — shows you know the theoretical complexity

Follow-up Questions#

• How would you handle removeLand operations? — Union-Find does not support splits; use offline processing reversed
• What if operations come in a stream? — Same solution works; process one at a time
• How would you parallelize this? — Concurrent Union-Find requires lock-free CAS operations
• What if it is a 3D grid? — Extend to 6 neighbors (up, down, left, right, front, back)
• Can you count islands without Union-Find? — Yes, BFS/DFS per operation but O(k * m * n) total

Key Takeaways#

• Union-Find with path compression and union by rank achieves O(alpha(N)) ≈ O(1) per operation
• Island count changes by +1 on new land creation and -1 for each successful merge with a neighbor
• Use a hash map for parent/rank when grid size is large to avoid O(m*n) initialization
• Duplicate addLand positions must be detected and skipped to avoid double-counting
• Amazon tests this to evaluate knowledge of dynamic connectivity and disjoint set data structures
• The pattern applies broadly: any problem involving "how many connected components after each join?" uses this approach
• This is LeetCode 305 — a hard problem that appears frequently in Amazon onsite rounds