beingsde
Sign In
Back to all DSA patterns
Union-Find•Pattern: Union-Find•Medium

Union-Find — connected components with dynamic union

Problem Intuition & Objective

Efficiently manage and query connected components with union-by-rank and path compression.

Time ComplexityO(α(n)) per op
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Disjoint Set Union with path compression + union by rank.

Core Invariants & Edge Cases

  • find() with path compression: O(α(n)) amortized
  • union() by rank prevents tall trees
  • Use for dynamic connectivity, minimum spanning tree (Kruskal's)
Previous ProblemBellman-Ford — detect negative weight cyclesNext Problem Flood fill algorithm

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.