Union Find Pattern: LeetCode Guide & Problems

Disjoint set union for grouping, connectivity, and cycle detection.

✓ Pattern Solutions & Guides Practice Mode Enabled

6 Problem 0 Easy 5 Medium 1 Hard

Overview

Union-Find (Disjoint Set Union) efficiently tracks connected components. With path compression and union by rank, operations are nearly O(1) amortized.

When to Use

Number of connected components
Redundant connection (cycle detection)
Accounts merge
Satisfiability of equality equations
Kruskal's MST algorithm

Common Mistakes

Forgetting path compression — makes find O(log n) without it
Union by rank vs union by size — either works, just be consistent
Not initializing parent[i] = i

Complexity

Time

O(α(n)) per operation — effectively O(1)

Space

O(n)

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }
}

Problems (6)

Hide completed

Problem	Difficulty	Companies	Freq	Solution
Redundant Connection #Graph #Union Find #DFS	Medium	GoogleAmazon	Medium	Solution
Accounts Merge #Graph #Union Find #DFS	Medium	FacebookAmazon +1	Medium	Solution
Number of Provinces #DFS #BFS #Union-Find	Medium	AmazonFacebook +1	High	Solution
Satisfiability of Equality Equations #Array #String #Union-Find	Medium	GoogleAmazon	Medium	Solution
Swim in Rising Water #Array #Binary Search #DFS	Hard	GoogleAmazon	Medium	Solution
Most Stones Removed with Same Row or Column #Hash Table #DFS #Union-Find	Medium	FacebookAmazon	Medium	Solution

🧠

Mastering the Union Find Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Union Find pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Union Find, the target time complexity is typically O(α(n)) per operation — effectively O(1) while maintaining an auxiliary space complexity of O(n). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.

Master Union-Find (DSU) for interviews: path compression, union by rank, cycle detection, connected …