Number of Islands II

hard union find matrix

Problem

An m×n grid of water starts empty. For each position addLand(r, c), return the count of islands after the operation.

Inputm=3, n=3, positions=[(0,0),(0,1),(1,2),(2,1)]

Output[1,1,2,3]

Adding (0,1) merges with (0,0) — count stays 1.

positions (r,c ;)

def num_islands_2(m, n, positions):
    parent = {}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    out, count = [], 0
    for r, c in positions:
        if (r, c) in parent:
            out.append(count); continue
        parent[(r, c)] = (r, c); count += 1
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nb = (r+dr, c+dc)
            if 0 <= nb[0] < m and 0 <= nb[1] < n and nb in parent:
                a, b = find((r, c)), find(nb)
                if a != b: parent[a] = b; count -= 1
        out.append(count)
    return out

function numIslands2(m, n, positions) {
  const parent = new Map();
  const find = x => { while (parent.get(x) !== x) { parent.set(x, parent.get(parent.get(x))); x = parent.get(x); } return x; };
  const out = []; let count = 0;
  for (const [r, c] of positions) {
    const k = r * n + c;
    if (parent.has(k)) { out.push(count); continue; }
    parent.set(k, k); count++;
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nk = nr * n + nc;
      if (!parent.has(nk)) continue;
      const a = find(k), b = find(nk);
      if (a !== b) { parent.set(a, b); count--; }
    }
    out.push(count);
  }
  return out;
}

class Solution {
    int[] parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    public List numIslands2(int m, int n, int[][] positions) {
        parent = new int[m * n]; Arrays.fill(parent, -1);
        List out = new ArrayList<>(); int count = 0;
        int[][] d = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] p : positions) {
            int k = p[0] * n + p[1];
            if (parent[k] != -1) { out.add(count); continue; }
            parent[k] = k; count++;
            for (int[] dd : d) {
                int nr = p[0] + dd[0], nc = p[1] + dd[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int nk = nr * n + nc;
                if (parent[nk] == -1) continue;
                int a = find(k), b = find(nk);
                if (a != b) { parent[a] = b; count--; }
            }
            out.add(count);
        }
        return out;
    }
}

class Solution {
    vector parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
public:
    vector numIslands2(int m, int n, vector>& positions) {
        parent.assign(m * n, -1);
        vector out; int count = 0;
        int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
        for (auto& p : positions) {
            int k = p[0] * n + p[1];
            if (parent[k] != -1) { out.push_back(count); continue; }
            parent[k] = k; count++;
            for (int i = 0; i < 4; i++) {
                int nr = p[0] + dr[i], nc = p[1] + dc[i];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int nk = nr * n + nc;
                if (parent[nk] == -1) continue;
                int a = find(k), b = find(nk);
                if (a != b) { parent[a] = b; count--; }
            }
            out.push_back(count);
        }
        return out;
    }
};

Explanation

We are adding land one cell at a time, and after each add we want the running number of islands. The key tool is a union-find (disjoint set), which lets us quickly group cells that touch into the same island.

The simple rule: every time we turn a water cell into land, we add 1 to the island count, because a brand-new piece of land is its own island at first. Then we look at its four neighbors; for each neighbor that is already land and not yet joined to us, we union the two and subtract 1, because two separate islands just merged into one.

The find function returns the "root" representative of a cell's group. Two cells belong to the same island exactly when they share a root. We only subtract when a != b (their roots differ), so merging cells that were already connected does not double-count.

Example: positions = [(0,0),(0,1),(1,2),(2,1)]. Add (0,0) → count 1. Add (0,1): it touches (0,0), so union and subtract → count stays 1. Add (1,2): no land neighbor → count 2. Add (2,1): no land neighbor → count 3. Output is [1,1,2,3].

Because union-find operations are almost constant time, processing all k additions is very fast even on a big grid.

Time: O(k · α(mn)) Space: O(mn)