Union Find Practice Questions
Eight interview classics. Every flavor of the DSU pattern is represented: plain connectivity, cycle detection, weighted offsets, grid encoding, equality constraints.
Before reading any solution, force yourself through the pattern-spotting checklist:
- Groups / equivalence classes?
- Only edge additions (no removals)?
- Connectivity, not paths?
- Pairs arriving as a stream?
- Cycle detection in disguise?
Five questions. The whole chapter, condensed.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Number of Provinces | Component counting on an adjacency matrix | Available |
| Number of Connected Components in an Undirected Graph | Component counting from edge list | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Graph Valid Tree | Connectivity + cycle detection | Available |
| Redundant Connection | Cycle detection on a stream of edges | Available |
| Satisfiability of Equality Equations | Equality constraints as unions, contradictions as cross-component checks | Available |
| Smallest String With Swaps | Group indices into equivalence classes, sort within each | Available |
| Regions Cut By Slashes | Subdivide each cell into 4 triangles and DSU them | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Evaluate Division | Weighted DSU — multiplicative offsets | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Most Stones Removed With Same Row/Col | Implicit DSU on rows ⊎ columns | Coming Soon |
| Accounts Merge | DSU over accounts indexed by shared email | Coming Soon |
| Number of Islands II | Dynamic island merging as cells turn on | Coming Soon |
| Bricks Falling When Hit | Offline reverse — turn deletions into insertions | Coming Soon |
| Possible Bipartition | DSU with parity / 2-coloring | Coming Soon |
| Number of Operations to Make Network Connected | Components vs spare edges | Coming Soon |
| Lexicographically Smallest Equivalent String | DSU keeping the smallest root | Coming Soon |
| Synonymous Sentences | DSU on synonym pairs + DFS | Coming Soon |