Number of Islands II - Online Queries using DSU

Problem and examples

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.

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

How it works

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.

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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

int find(int parent[], int i) {
    if (parent[i] == -1) return i;
    return parent[i] = find(parent, parent[i]);
}

int unionSets(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    if (xset != yset) {
        parent[xset] = yset;
        return 1;
    }
    return 0;
}

int* numIslands2(int n, int m, int operators[][2], int k, int* returnSize) {
    int* parent = (int*)malloc(sizeof(int) * n * m);
    for (int i = 0; i < n * m; i++) parent[i] = -1;

    int* grid = (int*)calloc(n * m, sizeof(int));
    int* result = (int*)malloc(sizeof(int) * k);
    int count = 0;
    int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

    for (int i = 0; i < k; i++) {
        int r = operators[i][0], c = operators[i][1];
        int id = r * m + c;
        if (grid[id] == 1) {
            result[i] = count;
            continue;
        }
        grid[id] = 1;
        count++;
        for (int d = 0; d < 4; d++) {
            int nr = r + directions[d][0], nc = c + directions[d][1];
            int nid = nr * m + nc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nid] == 1) {
                if (unionSets(parent, id, nid)) count--;
            }
        }
        result[i] = count;
    }
    free(parent);
    free(grid);
    *returnSize = k;
    return result;
}

int main() {
    int operators[][2] = {{0,0}, {0,1}, {1,2}, {2,1}};
    int returnSize = 0;
    int* res = numIslands2(3, 3, operators, 4, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

vector<int> numIslands2(int n, int m, vector<pair<int,int>> operators) {
    DSU dsu(n * m);
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<int> result;
    int count = 0;
    vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};

    for (auto& op : operators) {
        int r = op.first, c = op.second;
        if (grid[r][c] == 1) {
            result.push_back(count);
            continue;
        }
        grid[r][c] = 1;
        count++;
        int id = r * m + c;
        for (auto& dir : directions) {
            int nr = r + dir.first, nc = c + dir.second;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1) {
                int nid = nr * m + nc;
                if (dsu.unionSets(id, nid)) count--;
            }
        }
        result.push_back(count);
    }
    return result;
}

int main() {
    vector<pair<int,int>> ops = {{0,0},{0,1},{1,2},{2,1}};
    vector<int> res = numIslands2(3, 3, ops);
    for (int x : res) cout << x << ' ';
    cout << endl;
    return 0;
}

Python implementation

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

def numIslands2(n, m, operators):
    dsu = DSU(n * m)
    grid = [[0]*m for _ in range(n)]
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    result = []
    count = 0

    for r, c in operators:
        if grid[r][c] == 1:
            result.append(count)
            continue
        grid[r][c] = 1
        count += 1
        id = r * m + c
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 1:
                nid = nr * m + nc
                if dsu.union(id, nid):
                    count -= 1
        result.append(count)
    return result

if __name__ == '__main__':
    operators = [(0,0), (0,1), (1,2), (2,1)]
    print(numIslands2(3, 3, operators))  # Output: [1, 1, 2, 3]

Java implementation

import java.util.*;

class DSU {
    int[] parent, rank;
    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

public class IslandCounter {
    public static List<Integer> numIslands2(int n, int m, int[][] operators) {
        DSU dsu = new DSU(n * m);
        int[][] grid = new int[n][m];
        List<Integer> result = new ArrayList<>();
        int count = 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

        for (int[] op : operators) {
            int r = op[0], c = op[1];
            if (grid[r][c] == 1) {
                result.add(count);
                continue;
            }
            grid[r][c] = 1;
            count++;
            int id = r * m + c;
            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1) {
                    int nid = nr * m + nc;
                    if (dsu.union(id, nid)) count--;
                }
            }
            result.add(count);
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] ops = {{0,0}, {0,1}, {1,2}, {2,1}};
        List<Integer> res = numIslands2(3, 3, ops);
        for (int x : res) System.out.print(x + " ");
        System.out.println();
    }
}

JavaScript implementation

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]

Go implementation

package main

import "fmt"

type DSU struct {
    parent []int
    rank   []int
}

func NewDSU(n int) *DSU {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &DSU{parent, rank}
}

func (d *DSU) find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.find(d.parent[x])
    }
    return d.parent[x]
}

func (d *DSU) union(x, y int) bool {
    rootX := d.find(x)
    rootY := d.find(y)
    if rootX == rootY {
        return false
    }
    if d.rank[rootX] < d.rank[rootY] {
        d.parent[rootX] = rootY
    } else if d.rank[rootX] > d.rank[rootY] {
        d.parent[rootY] = rootX
    } else {
        d.parent[rootY] = rootX
        d.rank[rootX]++
    }
    return true
}

func numIslands2(n, m int, operators [][2]int) []int {
    dsu := NewDSU(n * m)
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, m)
    }
    dirs := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
    result := []int{}
    count := 0

    for _, op := range operators {
        r, c := op[0], op[1]
        if grid[r][c] == 1 {
            result = append(result, count)
            continue
        }
        grid[r][c] = 1
        count++
        id := r * m + c
        for _, d := range dirs {
            nr, nc := r + d[0], c + d[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 {
                nid := nr * m + nc
                if dsu.union(id, nid) {
                    count--
                }
            }
        }
        result = append(result, count)
    }
    return result
}

func main() {
    ops := [][2]int{{0,0}, {0,1}, {1,2}, {2,1}}
    res := numIslands2(3, 3, ops)
    for _, v := range res {
        fmt.Printf("%d ", v)
    }
    fmt.Println()
}

Rust implementation

fn find(parent: &mut Vec<usize>, x: usize) -> usize {
    if parent[x] != x {
        parent[x] = find(parent, parent[x]);
    }
    parent[x]
}

fn union(parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) -> bool {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x == root_y {
        return false;
    }
    if rank[root_x] < rank[root_y] {
        parent[root_x] = root_y;
    } else if rank[root_x] > rank[root_y] {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x] += 1;
    }
    true
}

fn num_islands2(n: usize, m: usize, operators: &Vec<(usize, usize)>) -> Vec<usize> {
    let mut parent: Vec<usize> = (0..n*m).collect();
    let mut rank = vec![0; n*m];
    let mut grid = vec![vec![0; m]; n];
    let directions = vec![(-1,0),(1,0),(0,-1),(0,1)];
    let mut result = Vec::new();
    let mut count = 0;

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

        for &(dr, dc) in directions.iter() {
            let nr = r as isize + dr;
            let nc = c as isize + dc;
            if nr >= 0 && nr < n as isize && nc >= 0 && nc < m as isize {
                let nr = nr as usize;
                let nc = nc as usize;
                if grid[nr][nc] == 1 {
                    let nid = nr * m + nc;
                    if union(&mut parent, &mut rank, id, nid) {
                        count -= 1;
                    }
                }
            }
        }
        result.push(count);
    }
    result
}

fn main() {
    let operators = vec![(0,0),(0,1),(1,2),(2,1)];
    let res = num_islands2(3, 3, &operators);
    for val in res {
        print!("{} ", val);
    }
    println!();
}

Kotlin implementation

class DSU(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n)

    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    fun union(x: Int, y: Int): Boolean {
        val rootX = find(x)
        val rootY = find(y)
        if (rootX == rootY) return false
        when {
            rank[rootX] < rank[rootY] -> parent[rootX] = rootY
            rank[rootX] > rank[rootY] -> parent[rootY] = rootX
            else -> {
                parent[rootY] = rootX
                rank[rootX]++
            }
        }
        return true
    }
}

fun numIslands2(n: Int, m: Int, operators: List<Pair<Int, Int>>): List<Int> {
    val dsu = DSU(n * m)
    val grid = Array(n) { IntArray(m) }
    val directions = listOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1))
    val result = mutableListOf<Int>()
    var count = 0

    for ((r, c) in operators) {
        if (grid[r][c] == 1) {
            result.add(count)
            continue
        }
        grid[r][c] = 1
        count++
        val id = r * m + c
        for ((dr, dc) in directions) {
            val nr = r + dr
            val nc = c + dc
            if (nr in 0 until n && nc in 0 until m && grid[nr][nc] == 1) {
                val nid = nr * m + nc
                if (dsu.union(id, nid)) count--
            }
        }
        result.add(count)
    }
    return result
}

fun main() {
    val operators = listOf(Pair(0,0), Pair(0,1), Pair(1,2), Pair(2,1))
    val res = numIslands2(3, 3, operators)
    println(res.joinToString(" "))
}

Swift implementation

class DSU {
    var parent: [Int]
    var rank: [Int]

    init(_ n: Int) {
        parent = Array(0..<n)
        rank = Array(repeating: 0, count: n)
    }

    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    func union(_ x: Int, _ y: Int) -> Bool {
        let rootX = find(x)
        let rootY = find(y)
        if rootX == rootY { return false }

        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else {
            parent[rootY] = rootX
            rank[rootX] += 1
        }
        return true
    }
}

func numIslands2(_ n: Int, _ m: Int, _ operators: [[Int]]) -> [Int] {
    let dsu = DSU(n * m)
    var grid = Array(repeating: Array(repeating: 0, count: m), count: n)
    let directions = [(-1,0),(1,0),(0,-1),(0,1)]
    var result = [Int]()
    var count = 0

    for op in operators {
        let r = op[0], c = op[1]
        if grid[r][c] == 1 {
            result.append(count)
            continue
        }
        grid[r][c] = 1
        count += 1
        let id = r * m + c

        for (dr, dc) in directions {
            let nr = r + dr
            let nc = c + dc
            if nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 {
                let nid = nr * m + nc
                if dsu.union(id, nid) {
                    count -= 1
                }
            }
        }
        result.append(count)
    }
    return result
}

let ops = [[0,0],[0,1],[1,2],[2,1]]
let res = numIslands2(3, 3, ops)
print(res.map { String($0) }.joined(separator: " "))

TypeScript implementation

class DSU {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

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

  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const 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: number, m: number, operators: [number, number][]): number[] {
  const dsu = new DSU(n * m);
  const grid: number[][] = Array.from({ length: n }, () => Array(m).fill(0));
  const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
  const result: number[] = [];
  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;
}

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