Number of Islands (Union-Find variant): union adjacent land cells

• Union-Find variant of Number of Islands treats each land cell as a disjoint-set element.
• Initial count equals the number of land cells, since each starts as its own island.
• Merge step unions each land cell with its right and down land neighbors, decrementing the count on each successful merge.
• Right-and-down only avoids double-processing each adjacent pair.
• 1D index is row * cols + col to flatten the 2D grid for the parent array.
• Time is effectively O(rows * cols); space is O(rows * cols) for the parent and rank arrays.

What is the Union-Find variant of Number of Islands?

Given a 2D grid of '1' (land) and '0' (water), count the number of islands using Union-Find instead of DFS/BFS. An island is a group of land cells connected horizontally or vertically. This variant is especially useful when cells are added dynamically.

package com.bank.service;

public class CoverageRegionCounter {
    private int[] parent;
    private int[] rank;
    private int count;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        parent = new int[rows * cols];
        rank = new int[rows * cols];
        count = 0;

        // Initialize: each land cell is its own island
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    int idx = r * cols + c;
                    parent[idx] = idx;
                    count++;
                }
            }
        }

        // Union adjacent land cells (right and down only)
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    int idx = r * cols + c;
                    if (c + 1 < cols && grid[r][c + 1] == '1') {
                        union(idx, idx + 1);
                    }
                    if (r + 1 < rows && grid[r + 1][c] == '1') {
                        union(idx, idx + cols);
                    }
                }
            }
        }
        return count;
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        count--;
    }
}

Why check only right and down?

If you check all four directions (up, down, left, right), each pair of adjacent land cells is processed twice. Checking only right and down ensures each pair is visited exactly once, which is both correct and efficient.

Grid:  1 1 0
       1 0 0
       0 0 1

Cell (0,0): check right (0,1)=land → union
            check down  (1,0)=land → union
Cell (0,1): check right (0,2)=water → skip
            check down  (1,1)=water → skip
Cell (1,0): check right (1,1)=water → skip
            check down  (2,0)=water → skip
Cell (2,2): check right → out of bounds
            check down  → out of bounds

Initial count: 4 land cells
After union(0,0)-(0,1): count = 3
After union(0,0)-(1,0): count = 2
Final: 2 islands

How does the 1D index flattening work?

A 2D cell at (row, col) maps to row * cols + col in a 1D array. This is the standard row-major order. The right neighbor at (row, col+1) maps to idx + 1, and the down neighbor at (row+1, col) maps to idx + cols.

int idx = r * cols + c;         // current cell
int rightIdx = idx + 1;          // right neighbor
int downIdx = idx + cols;        // down neighbor

How is this different from the DFS flood-fill approach?

| Aspect | DFS Flood Fill | Union-Find |
|--------|---------------|------------|
| Approach | Mark visited, explore connected | Merge adjacent land cells |
| Data structure | Recursion stack or explicit stack | Parent and rank arrays |
| Dynamic cells | Must re-scan entire grid | O(alpha) per new cell |
| Stack overflow risk | Yes on huge islands | No |
| Code complexity | Simpler | Moderate |

When does Union-Find shine?

Union-Find shines in the dynamic variant (Number of Islands II) where land cells are added one at a time and you need the island count after each addition. With DFS, you would need to re-scan the grid after every addition. With Union-Find, you add the new cell, union it with its existing land neighbors, and the count updates in near-constant time.

// Dynamic variant sketch
public int addLand(int row, int col) {
    int idx = row * cols + col;
    parent[idx] = idx;
    count++;
    // Union with existing land neighbors (up, down, left, right)
    if (row > 0 && isLand(row-1, col)) union(idx, (row-1)*cols+col);
    if (row < rows-1 && isLand(row+1, col)) union(idx, (row+1)*cols+col);
    if (col > 0 && isLand(row, col-1)) union(idx, row*cols+col-1);
    if (col < cols-1 && isLand(row, col+1)) union(idx, row*cols+col+1);
    return count;
}

What are edge cases?

• Empty grid: return 0.
• All water: return 0 (no land cells, count stays at 0).
• All land: return 1 (every cell merges into one island).
• Single cell grid with '1': return 1.

// Edge case: all land
// Grid: 1 1
//        1 1
// Initial count: 4
// union(0,1): 3, union(0,2): 2, union(1,3): 1
// Final: 1 island

What are common mistakes?

The first mistake is initializing the parent array for water cells, which inflates the count. Only initialize land cells. The second mistake is checking all four directions instead of just right and down, which double-counts merges. The third mistake is forgetting path compression.

// WRONG: initialize all cells
for (int i = 0; i < rows * cols; i++) {
    parent[i] = i;  // includes water cells!
    count = rows * cols;  // wrong count
}

// CORRECT: initialize only land cells
if (grid[r][c] == '1') {
    parent[idx] = idx;
    count++;
}

What should a senior engineer know?

At the National Bank of India, the planning team maintained a coverage grid where cells were switched on as new ATMs and branches opened. Union-Find was especially valuable because coverage cells were activated incrementally, and the structure gave the running region count without re-scanning the whole map. DFS would have required a full grid traversal after every new branch opening, which was unacceptable for real-time dashboard updates.