Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardunion-find

Number of Islands II

Problem (restated)

m×n water grid. positions turn cells to land one by one. After each add, return the current number of islands (4-connected land).

Intuition

Each new land starts as its own island (+1), then unions with already-land neighbors and decrements count when components merge.

Approaches

Online Union-Find on grid

Unverified

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

Idea. Flatten cell id = r*n+c. parent[id]=-1 means water. Skip duplicate positions.

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

Trade-offs. Offline reverse UF also works; online is the natural interview path.

Solution

export function numIslands2(m: number, n: number, positions: number[][]): number[] {
  const parent = Array(m * n).fill(-1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  let count = 0;
  const res: number[] = [];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (const p of positions) {
    const r = p[0]!, c = p[1]!;
    const id = r * n + c;
    if (parent[id] !== -1) {
      res.push(count);
      continue;
    }
    parent[id] = id;
    count++;
    for (const d of dirs) {
      const nr = r + d[0]!, nc = c + d[1]!;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nid = nr * n + nc;
      if (parent[nid] === -1) continue;
      const a = find(id), b = find(nid);
      if (a !== b) {
        parent[b] = a;
        count--;
      }
    }
    res.push(count);
  }
  return res;
}

export function numIslands2(m: number, n: number, positions: number[][]): number[] {
  const parent = Array(m * n).fill(-1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  let count = 0;
  const res: number[] = [];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (const p of positions) {
    const r = p[0]!, c = p[1]!;
    const id = r * n + c;
    if (parent[id] !== -1) {
      res.push(count);
      continue;
    }
    parent[id] = id;
    count++;
    for (const d of dirs) {
      const nr = r + d[0]!, nc = c + d[1]!;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nid = nr * n + nc;
      if (parent[nid] === -1) continue;
      const a = find(id), b = find(nid);
      if (a !== b) {
        parent[b] = a;
        count--;
      }
    }
    res.push(count);
  }
  return res;
}

Template connection

Dynamic connectivity with Union-Find.

Reflection

When water turns to land, union it with up to four land neighbors. After each add, append the component count.
The same cell a second time does not raise the count. A diagonal neighbor is not unioned.
The first land is 1. Two adjacent lands fall back to 1 on the second step.