Making a Large Island - Disjoint Set Union (DSU)

An in-depth pedagogical study note on solving the "Making a Large Island" problem using the Disjoint Set Union (DSU) data structure, optimized for maximum performance and interview readiness.

1. Why Do We Need This? (Problem Statement & Status Quo)

Problem Overview

You are given an $N \times N$ binary grid consisting of 0s and 1s. You are allowed to change at most one cell in the grid from a 0 to a 1. Your objective is to find the size of the largest group of connected 1s (connected components) after making this single modification.

Definition of Connected Cells

Two cells are considered connected if and only if:

They are adjacent to each other (sharing a common side: top, right, bottom, or left). Diagonal connections are strictly disallowed.
Both cells contain the value 1.

The Naive Brute-Force Approach vs. The Bottleneck

Naive Strategy: Iterate through every single 0 in the grid, temporarily flip it to a 1, run a Breadth-First Search (BFS) or Depth-First Search (DFS) to measure the size of the resulting connected component, and then flip it back.
Why it fails (Time Limit Exceeded): For an $N \times N$ matrix, there could be up to $N^2$ zeros. Running a full graph traversal ( $O(N^2)$ ) for every single zero results in an astronomical time complexity of $O(N^4)$ , which is far too slow for large constraints ( $N \approx 500$ ).
The Better Path: We need a way to pre-cluster existing components of 1s and dynamically query or merge them in near constant time. This requires the Disjoint Set Union (DSU) data structure.

2. Core Mental Model & Analogies

Real-Life Analogy: The Island Archipelagos and Bridge Building

Real-Life Analogy: Imagine an ocean filled with separated island chains (connected components of 1s). Each island has a known landmass size. The water cells (0s) represent building sites where you can construct a single bridge. If you place a bridge on a specific water cell, it might connect up to 4 neighboring islands (North, South, East, West). By dropping a bridge there, you instantly merge those separate island landmasses plus your newly built bridge (+1) into one massive super-archipelago.

Structure & Concept Flow

[ Island A (Size 6) ] <--- Water Cell (0) ---> [ Island B (Size 6) ]

Build a bridge here!

[ Merged Super-Archipelago: 6 + 6 + 1 = 13 ]

3. Mapping 2D Grid Cells to 1D Node Numbers

The Disjoint Set Union (DSU) data structure operates on linear integer identifiers (nodes from 0 to N*M - 1), whereas our grid uses 2D coordinates (row, col). We must bridge this gap by establishing a deterministic mapping formula.

Zero-Based Indexing Formula

For an $N \times N$ grid, total cells = $N^2$ . For any cell located at (row, col), its unique 1D node number is calculated as:

\text{Node Number} = (\text{row} \times \text{number of columns}) + \text{col}

CODE

Row 0: [0][1][2][3][4]          (Starts at row * 5 + col)
Row 1: [5][6][7][8][9]
Row 2: [10][11][12][13][14]
...

Example: If we are on row 4, column 2 in a 5-column grid:

\text{Node Number} = (4 \times 5) + 2 = 20 + 2 = 22

4. Step-by-Step Algorithm Evolution

To solve this problem efficiently without re-traversing the graph repeatedly, we execute a two-phase algorithm:

Phase 1: Pre-clustering (DSU Union):
- Iterate through every cell in the grid. If a cell contains 1, examine its 4 neighbors (top, right, bottom, left). If a neighbor also contains 1, union them using DSU (specifically Union by Size).
- At the end of Phase 1, all connected components of 1s are formed, and their root parents store the exact total size of their respective components in a size array.
Phase 2: Evaluating Every Zero (0):
- Iterate through every cell in the grid containing 0.
- Inspect its 4 directional neighbors. If a neighbor contains 1, find its ultimate DSU parent.
- Collect these ultimate parents into a data structure to avoid duplicate counting (crucial edge case!).
- Sum up the sizes of all unique parent components, add 1 (for the converted zero cell itself), and track the maximum island size found.

5. Handling Critical Edge Cases: Duplicate Parents

The Pitfall

Imagine a 0 cell that sits directly between two parts of the same large island (e.g., it touches the same component from both the top and the left). If you blindly sum the neighboring component sizes without deduplication, you will count the exact same island multiple times, yielding an artificially inflated, incorrect answer.

CODE

       [Top: Component #17 (Size 7)]
                     |
[Left: Component #17 (Size 7)] --- (0 Cell) --- [Right: Empty]
                     |
      [Bottom: Component #17 (Size 7)]

Naive Summation (Wrong): 7 + 7 + 7 + 1 = 22
Deduplicated Summation (Correct): 7 (counted once) + 1 = 8

The Solution: Using a Set

To prevent double-counting, we store the ultimate parent node IDs in a Set data structure before querying their sizes. Because sets automatically discard duplicate values, each unique connected component is counted exactly once.

6. Complete Implementation Code

Below are the production-grade implementations in Java and C++ demonstrating the DSU-based approach.

Java Implementation

JAVA

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 newr, int newc, int n) {
        return newr >= 0 && newr < n && newc >= 0 && newc < n;
    }

    public int largestIsland(int[][] grid) {
        int n = grid.length;
        DisjointSet ds = new DisjointSet(n * n);

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

        // Step 1: Connect all existing 1s
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 0) continue;
                for (int ind = 0; ind < 4; ind++) {
                    int newr = row + dr[ind];
                    int newc = col + dc[ind];
                    if (isValid(newr, newc, n) && grid[newr][newc] == 1) {
                        int nodeNo = row * n + col;
                        int adjNodeNo = newr * n + newc;
                        ds.unionBySize(nodeNo, adjNodeNo);
                    }
                }
            }
        }

        // Step 2: Try converting every 0 to 1 and calculate max island size
        int maxLen = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 1) continue;
                HashSet<Integer> components = new HashSet<>();
                for (int ind = 0; ind < 4; ind++) {
                    int newr = row + dr[ind];
                    int newc = col + dc[ind];
                    if (isValid(newr, newc, n)) {
                        if (grid[newr][newc] == 1) {
                            components.add(ds.findUPar(newr * n + newc));
                        }
                    }
                }

                int sizeTotal = 0;
                for (int parent : components) {
                    sizeTotal += ds.size.get(parent);
                }
                maxLen = Math.max(maxLen, sizeTotal + 1);
            }
        }

        // Edge case: If the grid is all 1s, the loops above won't check 0s
        for (int cellNo = 0; cellNo < n * n; cellNo++) {
            maxLen = Math.max(maxLen, ds.size.get(ds.findUPar(cellNo)));
        }

        return maxLen;
    }
}

C++ Implementation

C++

class DisjointSet {
public:
    vector<int> parent, size;
    DisjointSet(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

class Solution {
private:
    bool isValid(int newr, int newc, int n) {
        return newr >= 0 && newr < n && newc >= 0 && newc < n;
    }
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        DisjointSet ds(n * n);
        
        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};

        // Step 1: Connect components
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 0) continue;
                for (int ind = 0; ind < 4; ind++) {
                    int newr = row + dr[ind];
                    int newc = col + dc[ind];
                    if (isValid(newr, newc, n) && grid[newr][newc] == 1) {
                        int nodeNo = row * n + col;
                        int adjNodeNo = newr * n + newc;
                        ds.unionBySize(nodeNo, adjNodeNo);
                    }
                }
            }
        }

        // Step 2: Evaluate each zero cell
        int maxLen = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 1) continue;
                unordered_set<int> components;
                for (int ind = 0; ind < 4; ind++) {
                    int newr = row + dr[ind];
                    int newc = col + dc[ind];
                    if (isValid(newr, newc, n)) {
                        if (grid[newr][newc] == 1) {
                            components.insert(ds.findUPar(newr * n + newc));
                        }
                    }
                }

                int sizeTotal = 0;
                for (int parent : components) {
                    sizeTotal += ds.size[parent];
                }
                maxLen = max(maxLen, sizeTotal + 1);
            }
        }

        // Edge case: Grid contains all 1s
        for (int cellNo = 0; cellNo < n * n; cellNo++) {
            maxLen = max(maxLen, ds.size[ds.findUPar(cellNo)]);
        }

        return maxLen;
    }
};

7. Complexity Analysis

Resource	Complexity	Explanation
Time Complexity	$\mathcal{O}(N^2 \cdot \alpha(N^2))$	Traversing the grid twice takes $\mathcal{O}(N^2)$ operations. Path compression and union by size operate in nearly constant time ( $\alpha$ , the inverse Ackermann function). Set insertions for up to 4 neighbors take $\mathcal{O}(1)$ time.
Space Complexity	$\mathcal{O}(N^2)$	Required to store the DSU parent array, size array, and the 1D mapping of cell nodes across the $N \times N$ grid.

8. Summary and Key Takeaways

Dynamic Graph Modification: When problems involve altering graph structures dynamically (such as flipping a 0 to a 1), Disjoint Set Union (DSU) is the premier tool to maintain connected component sizes.
Coordinate Flattening: 2D grid cell coordinates (row, col) are efficiently mapped into a 1D integer space using the formula row * n + col.
Pre-Clustering Phase: Phase 1 unifies all adjacent 1s so that component sizes are pre-calculated and readily available in $\mathcal{O}(1)$ time.
Deduplication via Sets: Using a Set data structure when evaluating neighboring components around a zero prevents duplicate parent lookups and ensures correct mathematical summation.
All-Ones Edge Case: Always account for grids that contain no zeros (all 1s), ensuring the global maximum check scans all DSU roots at the end.