Number of Islands - II Online Queries using DSU (Disjoint Set Union)

Problem Statement❯

In this problem, you're given a 2D grid of size n × m, initially filled with water (all cells are 0). You are also given k operations where each operation turns a water cell into land (i.e., changes a 0 to 1). After each operation, you must return the number of islands in the grid.

An island is defined as a group of land cells (1s) that are connected horizontally or vertically.

Your task is to simulate each operation in order and return the number of islands after each.

Examples❯

n	m	Operators	Result	Description
3	3	[[0,0], [0,1], [1,2], [2,1]]	[1, 1, 2, 3]	Each land addition creates a new island (no adjacent land)
3	3	[[0,0], [0,1], [1,1]]	[1, 1, 1]	All added lands become part of the same connected island
2	2	[[0,0], [0,1], [1,1], [1,0]]	[1, 1, 1, 1]	Gradual merge into one island
2	2	[[0,0], [0,0], [1,1]]	[1, 1, 2]	Repeated land on same cell doesn't change island count
1	1	[[0,0]]	[1]	Single cell island

Solution❯

Understanding the Problem

We are given a 2D grid of size n x m, where initially all cells are water. Over time, land is added to the grid at specific coordinates through a series of queries. Our goal is to report the number of islands after each land addition.

An island is a group of connected land cells (connected horizontally or vertically). As land is added, some cells may connect to form a larger island, or they may remain isolated.

The challenge lies in efficiently updating and keeping track of the number of islands after each addition, especially as the number of queries can be large.

Step-by-Step Solution with Example

step 1: Flatten the 2D Grid

To simplify union-find operations, we treat the 2D grid as a 1D array. Each cell can be represented as cell_id = row * m + col. This gives a unique index to each cell in the grid.

step 2: Initialize DSU

We create a Disjoint Set Union (DSU) structure, also known as Union-Find, to group connected land cells. Initially, all cells are water, so they are not part of any set.

step 3: Process Each Query

For each land addition query:

Convert the 2D coordinates to a 1D cell index.
If the cell is already land, skip it (no changes).
Otherwise, mark the cell as land and increment the island count.
Check its 4 neighbors (up, down, left, right). If a neighbor is land and belongs to a different set, merge the sets using union(). For each merge, decrease the island count by 1 since two separate islands became one.

step 4: Return Island Count After Each Query

After processing each query, record the current island count in the result list.

Example:

Let’s say n = 3, m = 3 and the queries are: [(0,0), (0,1), (1,2), (2,1), (1,1)].

Add (0,0): New land. Count = 1.
Add (0,1): New land. It's adjacent to (0,0), so union them. Count = 1.
Add (1,2): New isolated land. Count = 2.
Add (2,1): New isolated land. Count = 3.
Add (1,1): New land. It's adjacent to (0,1), (1,2), and (2,1). All three are in different sets. Union with all. Count goes from 4 → 3 → 2 → 1.

Edge Cases

Adding land to an already land cell: Should be skipped, no effect on count.
Adjacent lands already connected: Union will detect they’re in the same set; no change to count.
Land added at the borders: Ensure neighbor checks do not go out of bounds.

Finally

This problem is a perfect use case for Disjoint Set Union (DSU). It efficiently maintains groups of connected land cells and helps track how the number of islands evolves over time.

Using optimizations like path compression and union by rank, we can process each query in nearly constant time, making this approach scalable even for large grids and many queries.

Algorithm Steps❯

Initialize parent and rank arrays for DSU of size n × m.
Initialize a grid of size n × m with all zeros.
For each operator (x, y):

If the cell is already land, skip and append current island count.
Mark cell as land, increase island count by 1.
Check its 4 neighbors. If neighbor is land, perform union:

Find parent of current and neighbor cells.
If different, union them and decrease island count.

Append island count to result array.

Return result array.

Code

JavaScript

class DSU {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX === rootY) return false;
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}

function numIslands2(n, m, operators) {
  const dsu = new DSU(n * m);
  const grid = Array.from({ length: n }, () => Array(m).fill(0));
  const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
  const result = [];
  let count = 0;

  for (const [r, c] of operators) {
    if (grid[r][c] === 1) {
      result.push(count);
      continue;
    }
    grid[r][c] = 1;
    count++;
    const id = r * m + c;

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] === 1) {
        const nid = nr * m + nc;
        if (dsu.union(id, nid)) {
          count--;
        }
      }
    }
    result.push(count);
  }

  return result;
}

console.log(numIslands2(3, 3, [[0,0], [0,1], [1,2], [2,1]])); // Output: [1, 1, 2, 3]

⬅ Previous TopicAccounts Merge Problem using Disjoint Set Union

Next Topic ⮕Making a Large Island Using DSU

Comments

Loading comments...