Graph - DSA: Number of Islands - II - Online Queries - DSU

This chapter covers solving the classic "Number of Islands II" problem using the Disjoint Set Union (DSU) data structure. Unlike static grid problems where the entire matrix is given upfront, this problem processes online queries—where island cells are added dynamically one by one, and we must report the active island count after each operation.

1. Why Do We Need DSU for Online Queries?

• Status Quo in Static Islands: In standard static island problems, the entire grid is known beforehand, and we use standard Traversals (BFS/DFS) or a visited matrix to count components.
• The Dynamic Nature of Online Queries: Here, the grid starts completely empty (all sea). Queries arrive sequentially: "Build an island at coordinate $(r, c)$."
• The Challenge: If we ran a full BFS/DFS traversal from scratch for every single query, the time complexity would skyrocket ($O(Q \cdot N \cdot M)$), leading to Time Limit Exceeded (TLE) in an interview or online judge.
• The Solution: We need an algorithm capable of handling dynamic graph connectivity efficiently. Disjoint Set Union (DSU) allows us to merge components in nearly constant time ($\alpha(N)$), making it the ideal choice for incremental graph construction.

2. Core Mental Model: The Island Merge Game

• Real-Life Analogy: Imagine building an archipelago on an empty ocean.
  • When you drop land on an empty coordinate $(r, c)$, it initially stands alone as an individual island, increasing the total island count by $+1$.
  • However, if that newly dropped cell shares a horizontal or vertical side with an existing neighboring island, it acts as a bridge.
  • If the neighbor belongs to a different component, dropping this cell connects two previously separate islands into one, decreasing the total island count by $-1$.
  • If the neighbor belongs to the same component, no merger happens, and the count remains unchanged.

3. Cell-to-Node Flattening Formula

Disjoint Set data structures operate on 1D linear node identifiers (from $0$ to $N \cdot M - 1$), whereas our grid is 2D with dimensions $N$ rows and $M$ columns. We must convert any 2D coordinate $(row, col)$ into a unique 1D node ID.

The Conversion Formula

For a grid with $M$ columns, every row consumes exactly $M$ node indices. Therefore, the formula to convert a 2D coordinate to a 1D node index is:

Example Walkthrough ($N = 4, M = 5$):

• Cell $(0, 0) \rightarrow 0 \times 5 + 0 = 0$
• Cell $(1, 0) \rightarrow 1 \times 5 + 0 = 5$
• Cell $(2, 1) \rightarrow 2 \times 5 + 1 = 11$

Row 0: [ 0,  1,  2,  3,  4]  (Consumes indices 0 to 4)
Row 1: [ 5,  6,  7,  8,  9]  (Consumes indices 5 to 9)
Row 2: [10, 11, 12, 13, 14] (Consumes indices 10 to 14)
Row 3: [15, 16, 17, 18, 19] (Consumes indices 15 to 19)

4. Step-by-Step Algorithm Workflow

When a query query $[r, c]$ is processed:

1. Duplicate Check: Check if coordinate $(r, c)$ was already visited using a visited grid. If it was already an island, appending the current count again and moving on preserves state without redundant work.
2. Mark & Increment: Mark $(r, c)$ as visited in our tracking matrix and provisionally increment the island count by $+1$.
3. Explore 4-Directional Neighbors: Check all valid adjacent cells (Up, Right, Down, Left) using Delta arrays ($\Delta r, \Delta c$).
4. Connectivity Check & Union:
   • Verify if the adjacent cell is valid and already marked as an island (visited == true).
   • Find the ultimate parents of the current node and the neighbor using DSU (findUPar).
   • If their ultimate parents are different, they belong to separate components. Perform unionBySize and decrement the island count by $1$.
5. Record Result: Store the current island count in the answer list.

5. Direction Vectors and Boundary Validation

To check all four neighbors cleanly without writing repetitive code, we use directional delta arrays:

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

For any current cell $(r, c)$, the four neighbors are computed as:

• Up: row - 1, col (dr = -1, dc = 0)
• Right: row, col + 1 (dr = 0, dc = 1)
• Down: row + 1, col (dr = 1, dc = 0)
• Left: row, col - 1 (dr = 0, dc = -1)

Boundary Validation Helper

A neighbor cell $(\text{adjRow}, \text{adjCol})$ is valid if and only if it falls within the grid boundaries:

6. Complete Solution Implementation (Java & C++)

Java Implementation Structure

class DisjointSet {
    List<Integer> parent = new ArrayList<>();
    List<Integer> size = new ArrayList<>();

    public DisjointSet(int n) {
        for (int i = 0; i <= n; i++) {
            parent.add(i);
            size.add(1);
        }
    }

    public int findUPar(int node) {
        if (node == parent.get(node)) {
            return node;
        }
        int ulp = findUPar(parent.get(node));
        parent.set(node, ulp);
        return parent.get(node);
    }

    public void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size.get(ulp_u) < size.get(ulp_v)) {
            parent.set(ulp_u, ulp_v);
            size.set(ulp_v, size.get(ulp_v) + size.get(ulp_u));
        } else {
            parent.set(ulp_v, ulp_u);
            size.set(ulp_u, size.get(ulp_u) + size.get(ulp_v));
        }
    }
}

class Solution {
    private boolean isValid(int adjR, int adjC, int n, int m) {
        return adjR >= 0 && adjR < n && adjC >= 0 && adjC < m;
    }

    public List<Integer> numOfIslands(int n, int m, int[][] operators) {
        DisjointSet ds = new DisjointSet(n * m);
        int[][] vis = new int[n][m];
        int cnt = 0;
        List<Integer> ans = new ArrayList<>();

        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};

        for (int[] it : operators) {
            int row = it[0];
            int col = it[1];

            if (vis[row][col] == 1) {
                ans.add(cnt);
                continue;
            }

            vis[row][col] = 1;
            cnt++;

            for (int i = 0; i < 4; i++) {
                int adjR = row + dr[i];
                int adjC = col + dc[i];

                if (isValid(adjR, adjC, n, m)) {
                    if (vis[adjR][adjC] == 1) {
                        int nodeNo = row * m + col;
                        int adjNodeNo = adjR * m + adjC;
                        if (ds.findUPar(nodeNo) != ds.findUPar(adjNodeNo)) {
                            cnt--;
                            ds.unionBySize(nodeNo, adjNodeNo);
                        }
                    }
                }
            }
            ans.add(cnt);
        }
        return ans;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Online Queries: Problems where inputs arrive dynamically and require immediate incremental answers are best solved using structures that support fast dynamic connectivity.
• DSU Utility: Disjoint Set Union shines in dynamic graphs where edges/connections are added incrementally over time.
• 2D-to-1D Mapping: Flatten grid coordinates $(r, c)$ into a unique linear node ID using the formula $\text{Node ID} = r \times M + c$.
• Component Counting Trick: Increment the island count by $+1$ upon encountering a fresh land cell, and decrement by $-1$ every time a successful DSU merge bridges two previously disconnected components.
• Idempotency via Visited Checks: Guard against redundant operations on already visited cells to ensure linear efficiency and correct component tracking.
• Interview Standout Quality: Encapsulating DSU logic inside a clean, dedicated modular class rather than cluttering the solution function demonstrates robust software engineering principles.