A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

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

Explanation:

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

✅ 1. Problem Explanation (In Simple Terms)

You are given:

An empty m x n grid (all water → represented as 0)
A list of positions where land is added one by one (i.e., changing 0 → 1)

Each time land is added:

It might create a new island
Or merge with adjacent islands

📘 Your task: After each addition, return the number of islands in the grid.

💡 2. Key Insights

Island merging = a dynamic connectivity problem.
- When new land touches another land, they become part of the same island.
Use Disjoint Set Union (DSU) / Union Find to efficiently:
- Track which land cell belongs to which island (via "parent")
- Merge two islands (union)
- Count distinct root parents → number of islands
Important DSU optimizations:
- Path compression (make find() faster)
- Union by rank or size
Since the grid is dynamic, only add positions to the DSU when a land is created.

🧠 3. Steps to Solve

Initialize a DSU class to track roots of land cells.
Maintain a 2D grid to track land vs water.
For each new position:
- If it's already land, skip (prevent duplicates)
- Else:
  - Mark as land
  - Count as 1 new island
  - Check all 4 neighbors:
    - If neighbor is land and in different island → union them (merge islands → count -= 1)
After each addition, append the current island count.

✅ 4. JavaScript Code (Well-Commented)

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill(-1); // -1 = water
    this.rank = Array(size).fill(0);
    this.count = 0; // number of islands
  }

  index(x, y, n) {
    return x * n + y;
  }

  addLand(x, y, n) {
    const i = this.index(x, y, n);
    if (this.parent[i] !== -1) return false; // already land
    this.parent[i] = i; // make its own root
    this.count++;
    return true;
  }

  find(i) {
    if (this.parent[i] !== i) {
      this.parent[i] = this.find(this.parent[i]); // path compression
    }
    return this.parent[i];
  }

  union(i, j) {
    const rootI = this.find(i);
    const rootJ = this.find(j);

    if (rootI === rootJ) return;

    // Union by rank
    if (this.rank[rootI] < this.rank[rootJ]) {
      this.parent[rootI] = rootJ;
    } else if (this.rank[rootI] > this.rank[rootJ]) {
      this.parent[rootJ] = rootI;
    } else {
      this.parent[rootJ] = rootI;
      this.rank[rootI]++;
    }

    this.count--; // two islands merged
  }
}

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} positions
 * @return {number[]}
 */
function numIslands2(m, n, positions) {
  const uf = new UnionFind(m * n);
  const result = [];
  const dirs = [[0,1],[1,0],[-1,0],[0,-1]];
  const grid = Array.from({ length: m }, () => Array(n).fill(0));

  for (const [x, y] of positions) {
    if (!uf.addLand(x, y, n)) {
      result.push(uf.count); // already land
      continue;
    }

    const index = uf.index(x, y, n);

    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (
        nx >= 0 && ny >= 0 && nx < m && ny < n &&
        grid[nx][ny] === 1
      ) {
        const neighborIndex = uf.index(nx, ny, n);
        uf.union(index, neighborIndex);
      }
    }

    grid[x][y] = 1; // mark as land
    result.push(uf.count);
  }

  return result;
}

🔍 5. Dry Run Example

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

→ After [0,0]: 1 island
→ After [0,1]: merged → 1 island
→ After [1,2]: new island → 2 islands
→ After [2,1]: new island → 3 islands

✅ Output: [1, 1, 2, 3]

⏱️ 6. Time & Space Complexity

Let:

p = number of positions
m * n = grid size

Each find and union is near O(1) (with path compression + union by rank)

Time Complexity: O(p * α(n * m)) (α is inverse Ackermann, ~constant)
Space Complexity: O(m * n) for Union-Find arrays

✅ Final Verdict

Elegant use of Union Find to solve dynamic island problems
Real-time island count updates in near constant time
Great problem to showcase DSU knowledge in interviews

Let me know if you want:

A visualized step-by-step simulation
A grid-printing utility to watch islands evolve
A DFS version (slower but illustrative)

Number of Islands II