Union Find

Last updated: Apr 3, 2026

0) Concept
0-0) Union-Find Variants
0-1) Key Optimizations
0-1) Types
0-2) Algorithm Pattern / Template
0-3) Pattern-Specific Code Examples
1) Example Problems with Code References
2) Diagrams
Basic Union Operations
Path Compression Visualization
Union by Rank Example
Path Compression in Action
3) Tips & Pitfalls
LC Examples
2-1) Redundant Connection (LC 684) — Union-Find Cycle Detection
2-2) Number of Provinces (LC 547) — Count Connected Components
2-3) Accounts Merge (LC 721) — Union-Find on Emails
2-4) Graph Valid Tree (LC 261) — Union-Find
2-5) Number of Connected Components in Undirected Graph (LC 323) — Union-Find
2-6) Surrounded Regions (LC 130) — Union-Find with Virtual Border Node
2-7) Smallest String with Swaps (LC 1202) — Union-Find + Sorting
2-8) Most Stones Removed with Same Row or Column (LC 947) — Union-Find
2-9) Satisfiability of Equality Equations (LC 990) — Union-Find
2-10) Number of Operations to Make Network Connected (LC 1319) — Union-Find
2-11) Longest Consecutive Sequence (LC 128) — HashSet O(N)
2-12) Smallest Subtree with all the Deepest Nodes (LC 865) — BFS + Union-Find Climb

Union Find

Efficiently determines connectivity between nodes in dynamic graphs
When to use it: Dynamic connectivity queries, cycle detection, MST algorithms, grouping elements
Key LeetCode problems: Graph Valid Tree, Number of Islands, Accounts Merge, Friend Circles
Data structures: Parent array, size/rank array for optimization
States: Connected components, parent-child relationships

Time Complexity: Nearly O(1) per operation with optimizations

0) Concept

0-0) Union-Find Variants

Quick Find vs Quick Union

Quick Find:

Find: O(1) - Direct array lookup
Union: O(n) - Update all elements in component
Use Case: When find operations greatly outnumber union operations
Implementation: Store component ID directly for each element

// Quick Find Implementation
class QuickFind {
    private int[] id;
    private int count; // number of components

    public QuickFind(int n) {
        id = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            id[i] = i; // Each element is its own component
        }
    }

    /**
     * time = O(1)
     * space = O(1)
     */
    public int find(int p) {
        return id[p]; // Direct lookup
    }

    /**
     * time = O(N)
     * space = O(1)
     */
    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);

        if (pID == qID) return;

        // Change all entries with id[p] to id[q]
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
        count--;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

Quick Union (with optimizations):

Find: O(α(n)) ≈ O(1) with path compression
Union: O(α(n)) ≈ O(1) with union by rank/size
Use Case: General purpose, balanced find/union operations
Implementation: Store parent pointers, build tree structure

Comparison:

Operation	Quick Find	Quick Union	Quick Union + Optimizations
Initialize	O(n)	O(n)	O(n)
Find	O(1)	O(n) worst	O(α(n)) ≈ O(1)
Union	O(n)	O(n) worst	O(α(n)) ≈ O(1)
Space	O(n)	O(n)	O(n)
Best For	Many finds	Balanced	General purpose

When to Use Quick Find:

Very rare union operations
Real-time find queries required
Small datasets where O(n) union is acceptable

When to Use Quick Union (Optimized):

Balanced mix of find and union operations
Large datasets (millions of elements)
Most practical applications (recommended)

0-1) Key Optimizations

Union Find achieves nearly O(1) performance through two critical optimizations:

Path Compression: Applied in find() operation

Makes each visited node point directly to the root
Flattens the tree structure during traversal
Recursive: parent[x] = find(parent[x])
Amortizes future lookups to O(1)

Union by Rank/Size: Applied in union() operation

Always attach smaller tree to larger tree’s root
Keeps tree height balanced (logarithmic)
Prevents degenerate linear chains
Can track either tree height (rank) or size (count)

Without these optimizations, operations degrade to O(n). With both, time complexity becomes O(α(n)) where α is the inverse Ackermann function (effectively constant).

0-1) Types

Basic Connectivity: Check if nodes are connected, count components
Cycle Detection: Determine if adding edge creates cycle
Dynamic MST: Kruskal’s algorithm for minimum spanning trees
Weighted Union Find: Handle ratios/weights between nodes (LC 399)
Grid Problems: 2D grid connectivity (Number of Islands variants)

0-2) Algorithm Pattern / Template

Core Operations:

find(x): Get root parent of x with path compression
union(x, y): Connect two nodes, return false if already connected
connected(x, y): Check if two nodes are in same component

Template (Union by Size):

class UnionFind {
    int[] parent, size;
    int components;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // Path Compression: flatten tree by making nodes point directly to root
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Compress path during recursion
        }
        return parent[x];
    }

    // Union by Size: attach smaller tree to larger tree
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false; // Already connected

        // Always attach smaller size to larger size
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
        components--;
        return true;
    }
}

Alternative Template (Union by Rank):

class UnionFind {
    int[] parent, rank;
    int components;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0; // Initial rank is 0
        }
    }

    // Path Compression: recursively flatten tree structure
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Make x point directly to root
        }
        return parent[x];
    }

    // Union by Rank: attach lower rank tree to higher rank tree
    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);

        // Already in the same component
        if (rootX == rootY) return;

        // Attach smaller rank tree to larger rank tree
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY; // X's tree becomes child of Y
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX; // Y's tree becomes child of X
        } else {
            // Equal ranks: attach either way, increment rank of new root
            parent[rootX] = rootY;
            rank[rootY]++;
        }
        components--;
    }
}

Key Differences: Size vs Rank

Union by Size: Tracks actual count of nodes in each tree
- Useful when you need component sizes
- Updates size after every union
Union by Rank: Tracks approximate tree height (upper bound)
- More space efficient (rank grows slowly)
- Rank only increases when merging equal-rank trees
- With path compression, rank != actual height

Edge Cases:

Single node graphs
Already connected nodes
Invalid indices

0-3) Pattern-Specific Code Examples

Pattern 1: Basic Connectivity - Cycle Detection

Problem: LC 261 - Graph Valid Tree

public boolean validTree(int n, int[][] edges) {
    // A tree must have exactly n-1 edges
    if (edges.length != n - 1) return false;

    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return false; // Cycle detected
        }
    }
    return true;
}

Pattern 2: Component Counting

Problem: LC 323 - Number of Connected Components

public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    int components = n;

    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            components--;
        }
    }
    return components;
}

Pattern 3: Find Redundant Edge (Cycle Detection)

Problem: LC 684 - Redundant Connection

public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);

    for (int[] edge : edges) {
        int x = edge[0], y = edge[1];
        if (!uf.union(x, y)) {
            return edge; // This edge creates a cycle
        }
    }
    return null;
}

Pattern 4: 2D Grid Connectivity

Problem: LC 200 - Number of Islands

public int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    UnionFind uf = new UnionFind(rows * cols);
    int islands = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                islands++;
                int idx = r * cols + c;

                // Check 4 directions
                int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && grid[nr][nc] == '1') {
                        int nidx = nr * cols + nc;
                        if (uf.union(idx, nidx)) {
                            islands--;
                        }
                    }
                }
            }
        }
    }
    return islands;
}

Pattern 5: Weighted Union Find (with Ratios)

Problem: LC 399 - Evaluate Division

class WeightedUnionFind {
    Map<String, String> parent;
    Map<String, Double> ratio; // ratio[x] = x / parent[x]

    public WeightedUnionFind() {
        parent = new HashMap<>();
        ratio = new HashMap<>();
    }

    public String find(String x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            ratio.put(x, 1.0);
        }
        if (!x.equals(parent.get(x))) {
            String originalParent = parent.get(x);
            parent.put(x, find(originalParent));
            ratio.put(x, ratio.get(x) * ratio.get(originalParent));
        }
        return parent.get(x);
    }

    public void union(String x, String y, double value) {
        String rootX = find(x);
        String rootY = find(y);
        if (!rootX.equals(rootY)) {
            parent.put(rootX, rootY);
            ratio.put(rootX, value * ratio.get(y) / ratio.get(x));
        }
    }

    public double query(String x, String y) {
        if (!parent.containsKey(x) || !parent.containsKey(y)) {
            return -1.0;
        }
        String rootX = find(x);
        String rootY = find(y);
        if (!rootX.equals(rootY)) return -1.0;
        return ratio.get(x) / ratio.get(y);
    }
}

public double[] calcEquation(List<List<String>> equations,
                              double[] values,
                              List<List<String>> queries) {
    WeightedUnionFind uf = new WeightedUnionFind();

    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0);
        String b = equations.get(i).get(1);
        uf.union(a, b, values[i]);
    }

    double[] results = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String c = queries.get(i).get(0);
        String d = queries.get(i).get(1);
        results[i] = uf.query(c, d);
    }
    return results;
}

Pattern 6: BFS + Union-Find Climb (Tree LCA)

Problem: LC 865 - Smallest Subtree with all the Deepest Nodes

Core Idea: Use BFS to find all deepest-level nodes and build a parent map, then repeatedly union each node with its parent and move upward until all converge to a single root — that root is the LCA
When to Use: Finding LCA of multiple target nodes in a tree when you prefer iterative bottom-up convergence over recursive post-order
Steps:
1. BFS to build parent map and identify deepestNodes (last level in BFS)
2. Put all deepest nodes in a Set
3. While set size > 1: replace each node with its parent (they converge upward)
4. The single remaining node is the LCA
Key Insight: This is essentially “climb from leaves to root” — all deepest nodes walk upward in lockstep until they meet at one ancestor
Trade-off vs DFS: More intuitive for iterative thinkers; DFS post-order approach (return (node, depth) pair) is more concise and commonly used
Similar Problems: LC 236 (LCA), LC 1123 (same as 865), LC 1644, LC 1650

// LC 865 - BFS + Parent-Climb approach (simplified Union-Find concept)
// time = O(N), space = O(N)
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    parent.put(root, null);
    List<TreeNode> level = new ArrayList<>();

    // Step 1: BFS to find deepest level + build parent map
    while (!q.isEmpty()) {
        int size = q.size();
        level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur);
            if (cur.left != null) { parent.put(cur.left, cur); q.offer(cur.left); }
            if (cur.right != null) { parent.put(cur.right, cur); q.offer(cur.right); }
        }
    }

    // Step 2: Climb upward until all deepest nodes converge
    Set<TreeNode> set = new HashSet<>(level);
    while (set.size() > 1) {
        Set<TreeNode> next = new HashSet<>();
        for (TreeNode node : set) next.add(parent.get(node));
        set = next;
    }
    return set.iterator().next();
}

1) Example Problems with Code References

Basic Connectivity & Component Counting

LC 200 – Number of Islands: Count connected components in 2D grid
- Java: leetcode_java/src/main/java/LeetCodeJava/DFS/NumberOfIslands.java:493
- Pattern: Grid to 1D conversion (row * cols + col), Union Find with 4-directional checks
LC 261 – Graph Valid Tree: Check if n-1 edges form exactly one component
- Java: leetcode_java/src/main/java/LeetCodeJava/BFS/GraphValidTree.java:36
- Pattern: Cycle detection, exactly n-1 edges validation
LC 323 – Number of Connected Components: Basic component counting
- Java: leetcode_java/src/main/java/LeetCodeJava/Graph/NumberOfConnectedComponentsUndirectedGraph.java:49
- Pattern: Track component count, decrement on successful union

Cycle Detection & Redundancy

LC 684 – Redundant Connection: Find edge that creates cycle in tree
- Java: leetcode_java/src/main/java/LeetCodeJava/Tree/RedundantConnection.java:50
- Pattern: Return first edge where union() fails (cycle detected)

Weighted Union Find

LC 399 – Evaluate Division: Weighted UF with ratios for equation solving
- Java: leetcode_java/src/main/java/LeetCodeJava/DFS/EvaluateDivision.java:421
- Pattern: Store ratios, path compression with ratio multiplication

Advanced Applications

LC 130 – Surrounded Regions: Use dummy node for boundary connected regions
LC 547 – Friend Circles: Find groups in friendship matrix
LC 721 – Accounts Merge: Group accounts by shared emails
LC 865 – Smallest Subtree with all Deepest Nodes: BFS + parent-climb to find LCA of deepest nodes
LC 886 – Possible Bipartition: Detect bipartite graph conflicts
LC 1135 – Connecting Cities: MST with Kruskal’s algorithm
LC 1319 – Network Connections: Minimum operations to connect all nodes

2) Diagrams

Basic Union Operations

Initial: [0] [1] [2] [3] [4]

After union(0,1): [0,1] [2] [3] [4]
                   1
                  /
                 0

After union(2,3): [0,1] [2,3] [4]
                   1     3
                  /     /
                 0     2

Path Compression Visualization

Before find(1):           After find(1):
     4 (root)                4 (root)
     |                      /|\
     3                     1 2 3
     |
     2
     |
     1

Call find(1):
- 1 → 2 → 3 → 4 (traversal)
- During return, compress: parent[1] = 4, parent[2] = 4, parent[3] = 4
- Result: All nodes point directly to root

Union by Rank Example

Initial state:
  0     1     2     3
rank: 0 0 0 0

union(0, 1):         union(2, 3):
    0                    2
   /                    /
  1                    3
rank[0] = 1         rank[2] = 1

union(0, 2):
    0 (rank=2)
   / \
  1   2
     /
    3

Why rank increased:
- rank[0] = 1, rank[2] = 1 (equal)
- Attach 2 to 0, increment rank[0] to 2

Path Compression in Action

Scenario: find(A) in chain A→B→C→D→E (root)

Step 1: Recursive calls
  find(A) calls find(B)
    find(B) calls find(C)
      find(C) calls find(D)
        find(D) calls find(E)
          find(E) returns E

Step 2: Path compression during return
  parent[D] = E
  parent[C] = E  ← Compression happens here
  parent[B] = E  ← Skip intermediate nodes
  parent[A] = E  ← Direct link to root

Result:
Before:  A → B → C → D → E
After:   A → E
         B → E
         C → E
         D → E

3) Tips & Pitfalls

Common Mistakes:

Forgetting Path Compression: Results in O(n) time instead of nearly O(1)

// WRONG: No path compression
public int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

// CORRECT: With path compression
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Flatten on return
    }
    return parent[x];
}

Not Tracking Component Count: Missing decrement in union operation

// WRONG: Forgot to decrement
public void union(int x, int y) {
    parent[find(x)] = find(y);
}

// CORRECT: Track components
public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        components--; // Important!
    }
}

Index Confusion: Mixing 0-based and 1-based indexing
Cycle Detection Timing: Checking after union instead of before

Wrong Parent Update: Updating node instead of root in union

// WRONG: Update x directly
parent[x] = parent[y];

// CORRECT: Update roots
int rootX = find(x), rootY = find(y);
parent[rootX] = rootY;

Confusing Rank with Size:
- Rank = approximate tree height (only increases when merging equal ranks)
- Size = actual node count (always increases by merged size)

How to Optimize:

Always use path compression in find operation
Union by size/rank to keep trees balanced
Track component count for quick queries
Use iterative find to avoid recursion overhead

Space vs Time Tradeoffs:

Basic UF: O(n) space, O(n) time per operation
With optimizations: O(n) space, O(α(n)) ≈ O(1) time per operation
α(n) is inverse Ackermann function, effectively constant for practical inputs

Key Patterns:

Cycle Detection: if (find(x) == find(y)) return false; // cycle
Component Counting: Track and decrement count on successful unions
2D Grid to 1D: Use row * cols + col for coordinate conversion
Dummy Nodes: Connect boundary elements to virtual node for easier processing
Weighted Relationships: Store ratios/distances for equation-like problems

When NOT to use Union Find:

Static graphs where DFS/BFS suffice
Need shortest paths (use Dijkstra/Floyd-Warshall)
Directed graph strongly connected components (use Tarjan’s)
Small graphs where simple adjacency checks work

LC Examples

2-1) Redundant Connection (LC 684) — Union-Find Cycle Detection

Add edges one by one; if two nodes are already connected, this edge is redundant.

// LC 684 - Redundant Connection
// IDEA: Union-Find — detect cycle; redundant edge connects already-connected nodes
// time = O(N * α(N)), space = O(N)
public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    int[] parent = new int[n + 1];
    for (int i = 0; i <= n; i++) parent[i] = i;
    for (int[] edge : edges) {
        if (find(parent, edge[0]) == find(parent, edge[1])) return edge;
        union(parent, edge[0], edge[1]);
    }
    return new int[]{};
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]); // path compression
    return parent[x];
}
private void union(int[] parent, int x, int y) {
    parent[find(parent, x)] = find(parent, y);
}

2-2) Number of Provinces (LC 547) — Count Connected Components

Count the number of distinct roots after unioning all direct friendships.

// LC 547 - Number of Provinces
// IDEA: Union-Find — count distinct components (roots)
// time = O(N^2 * α(N)), space = O(N)
public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isConnected[i][j] == 1) union(parent, i, j);
    int count = 0;
    for (int i = 0; i < n; i++) if (find(parent, i) == i) count++;
    return count;
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}
private void union(int[] parent, int x, int y) {
    parent[find(parent, x)] = find(parent, y);
}

2-3) Accounts Merge (LC 721) — Union-Find on Emails

Union emails belonging to the same person; group by root; sort and format.

// LC 721 - Accounts Merge
// IDEA: Union-Find — union all emails in same account; group by root
// time = O(N * M * α(N*M)), space = O(N*M)
public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> parent = new HashMap<>();
    Map<String, String> emailToName = new HashMap<>();
    // init
    for (List<String> acc : accounts)
        for (int i = 1; i < acc.size(); i++) {
            parent.put(acc.get(i), acc.get(i));
            emailToName.put(acc.get(i), acc.get(0));
        }
    // union
    for (List<String> acc : accounts)
        for (int i = 2; i < acc.size(); i++)
            union(parent, acc.get(1), acc.get(i));
    // group by root
    Map<String, TreeSet<String>> groups = new HashMap<>();
    for (String email : parent.keySet())
        groups.computeIfAbsent(find(parent, email), k -> new TreeSet<>()).add(email);
    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<String, TreeSet<String>> entry : groups.entrySet()) {
        List<String> list = new ArrayList<>();
        list.add(emailToName.get(entry.getKey()));
        list.addAll(entry.getValue());
        result.add(list);
    }
    return result;
}
private String find(Map<String, String> parent, String x) {
    if (!parent.get(x).equals(x)) parent.put(x, find(parent, parent.get(x)));
    return parent.get(x);
}
private void union(Map<String, String> parent, String x, String y) {
    parent.put(find(parent, x), find(parent, y));
}

2-4) Graph Valid Tree (LC 261) — Union-Find

Tree has exactly N-1 edges and no cycle; union each edge, return false on same-component edge.

// LC 261 - Graph Valid Tree
// IDEA: Union-Find — N-1 edges + no cycle = valid tree
// time = O(N * α(N)), space = O(N)
public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    for (int[] e : edges) {
        if (find(p, e[0]) == find(p, e[1])) return false;
        p[find(p, e[0])] = find(p, e[1]);
    }
    return true;
}
private int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }

2-5) Number of Connected Components in Undirected Graph (LC 323) — Union-Find

Union each edge; count remaining distinct roots as connected components.

// LC 323 - Number of Connected Components in Undirected Graph
// IDEA: Union-Find — count distinct roots after unioning all edges
// time = O(N * α(N)), space = O(N)
public int countComponents(int n, int[][] edges) {
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    int components = n;
    for (int[] e : edges) {
        int a = find(p, e[0]), b = find(p, e[1]);
        if (a != b) { p[a] = b; components--; }
    }
    return components;
}
private int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }

2-6) Surrounded Regions (LC 130) — Union-Find with Virtual Border Node

Union all border ‘O’ cells to a virtual node; any ‘O’ not connected gets flipped to ‘X’.

// LC 130 - Surrounded Regions
// IDEA: Union-Find — connect border O cells to virtual node; flip disconnected O cells
// time = O(M*N), space = O(M*N)
public void solve(char[][] board) {
    int m = board.length, n = board[0].length, virtual = m * n;
    int[] p = new int[virtual + 1];
    for (int i = 0; i <= virtual; i++) p[i] = i;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (board[i][j] == 'O') {
        int id = i * n + j;
        if (i == 0 || i == m-1 || j == 0 || j == n-1) union(p, id, virtual);
        else for (int[] d : dirs) {
            int ni = i+d[0], nj = j+d[1];
            if (board[ni][nj] == 'O') union(p, id, ni*n+nj);
        }
    }
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
        if (board[i][j] == 'O' && find(p, i*n+j) != find(p, virtual)) board[i][j] = 'X';
}
private int find(int[] p, int x) { return p[x]==x ? x : (p[x]=find(p,p[x])); }
private void union(int[] p, int x, int y) { p[find(p,x)] = find(p,y); }

2-7) Smallest String with Swaps (LC 1202) — Union-Find + Sorting

Union swap pairs; sort characters within each component; place sorted chars back.

// LC 1202 - Smallest String with Swaps
// IDEA: Union-Find — group indices; sort chars in each group and reassign
// time = O(N log N), space = O(N)
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    int n = s.length();
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    for (List<Integer> pair : pairs) union(p, pair.get(0), pair.get(1));
    Map<Integer, List<Integer>> groups = new HashMap<>();
    for (int i = 0; i < n; i++) groups.computeIfAbsent(find(p, i), k -> new ArrayList<>()).add(i);
    char[] res = s.toCharArray();
    for (List<Integer> idx : groups.values()) {
        char[] chars = new char[idx.size()];
        for (int i = 0; i < idx.size(); i++) chars[i] = s.charAt(idx.get(i));
        Arrays.sort(chars);
        Collections.sort(idx);
        for (int i = 0; i < idx.size(); i++) res[idx.get(i)] = chars[i];
    }
    return new String(res);
}
private int find(int[] p, int x) { return p[x]==x ? x : (p[x]=find(p,p[x])); }
private void union(int[] p, int x, int y) { p[find(p,x)] = find(p,y); }

2-8) Most Stones Removed with Same Row or Column (LC 947) — Union-Find

Union stones in the same row or column; answer = stones − number of components.

// LC 947 - Most Stones Removed with Same Row or Column
// IDEA: Union-Find — stones sharing row/column are in same component; remove all but one
// time = O(N^2 * α(N)), space = O(N)
public int removeStones(int[][] stones) {
    int n = stones.length;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
                union(p, i, j);
    Set<Integer> roots = new HashSet<>();
    for (int i = 0; i < n; i++) roots.add(find(p, i));
    return n - roots.size();
}
private int find(int[] p, int x) { return p[x]==x ? x : (p[x]=find(p,p[x])); }
private void union(int[] p, int x, int y) { p[find(p,x)] = find(p,y); }

2-9) Satisfiability of Equality Equations (LC 990) — Union-Find

Process ‘==’ edges first; then check ‘!=’ pairs for contradiction.

// LC 990 - Satisfiability of Equality Equations
// IDEA: Union-Find — union on ==, validate != pairs for contradiction
// time = O(N), space = O(26)
public boolean equationsPossible(String[] equations) {
    int[] p = new int[26];
    for (int i = 0; i < 26; i++) p[i] = i;
    for (String eq : equations)
        if (eq.charAt(1) == '=') union(p, eq.charAt(0)-'a', eq.charAt(3)-'a');
    for (String eq : equations)
        if (eq.charAt(1) == '!' && find(p, eq.charAt(0)-'a') == find(p, eq.charAt(3)-'a'))
            return false;
    return true;
}
private int find(int[] p, int x) { return p[x]==x ? x : (p[x]=find(p,p[x])); }
private void union(int[] p, int x, int y) { p[find(p,x)] = find(p,y); }

2-10) Number of Operations to Make Network Connected (LC 1319) — Union-Find

Need at least N-1 edges; count components; extra edges reconnect disconnected components.

// LC 1319 - Number of Operations to Make Network Connected
// IDEA: Union-Find — count components; need (components-1) extra cables
// time = O(N * α(N)), space = O(N)
public int makeConnected(int n, int[][] connections) {
    if (connections.length < n - 1) return -1;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    int components = n;
    for (int[] c : connections) {
        int a = find(p, c[0]), b = find(p, c[1]);
        if (a != b) { p[a] = b; components--; }
    }
    return components - 1;
}
private int find(int[] p, int x) { return p[x]==x ? x : (p[x]=find(p,p[x])); }

2-11) Longest Consecutive Sequence (LC 128) — HashSet O(N)

For each number, only start counting if (num-1) is absent — marks sequence start.

// LC 128 - Longest Consecutive Sequence
// IDEA: HashSet — only extend sequences from their start element
// time = O(N), space = O(N)
public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int longest = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {   // sequence start
            int len = 1;
            while (set.contains(n + len)) len++;
            longest = Math.max(longest, len);
        }
    }
    return longest;
}

2-12) Smallest Subtree with all the Deepest Nodes (LC 865) — BFS + Union-Find Climb

BFS finds deepest nodes and parent map; then all deepest nodes “climb” upward via parents until they converge to the LCA. This is the same as LC 1123.

// LC 865 - Smallest Subtree with all the Deepest Nodes
// IDEA: BFS to find deepest level + build parent map, then climb upward until convergence
// time = O(N), space = O(N)
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    parent.put(root, null);
    List<TreeNode> level = new ArrayList<>();

    // BFS: build parent map, track each level (last level = deepest)
    while (!q.isEmpty()) {
        int size = q.size();
        level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur);
            if (cur.left != null) { parent.put(cur.left, cur); q.offer(cur.left); }
            if (cur.right != null) { parent.put(cur.right, cur); q.offer(cur.right); }
        }
    }

    // Climb: replace each node with its parent until all converge
    Set<TreeNode> set = new HashSet<>(level);
    while (set.size() > 1) {
        Set<TreeNode> next = new HashSet<>();
        for (TreeNode node : set) next.add(parent.get(node));
        set = next;
    }
    return set.iterator().next();
}

Union Find

Table of Contents