Union Find

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

6 problems 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 {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

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

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

Problems (6)

Hide completed

Problem	Difficulty	Companies	Freq
Redundant Connection	Medium	GoogleAmazon	Medium
Accounts Merge	Medium	FacebookAmazon +1	Medium
Number of Provinces	Medium	AmazonFacebook +1	High
Satisfiability of Equality Equations	Medium	GoogleAmazon	Medium
Swim in Rising Water	Hard	GoogleAmazon	Medium
Most Stones Removed with Same Row or Column	Medium	FacebookAmazon	Medium

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee