Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Build a minimum spanning tree by sorting all edges by weight and adding each edge that connects two so-far-separate components, skipping edges that would form a cycle. Union-Find with path compression and union by rank tells you in near-O(1) whether two endpoints are already connected. O(E log E) dominated by the sort.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you pair the greedy 'lightest safe edge' idea with Union-Find, and whether you can implement path compression and union by rank correctly rather than a naive O(n) find.
Where candidates slip
A naive Union-Find without path compression/rank (O(n) per find), or forgetting the cycle check and adding an edge that creates a loop.
How to stand out
State the cut property that justifies the greedy choice, implement both Union-Find optimizations, and detect disconnection by counting picked edges against V − 1.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Bold green edges (2-3, 0-3, 0-1) form the MST of total weight 19; edge 0-2 is excluded.
How to read it:find follows parent pointers to the root; union by rank attaches the shorter tree under the taller.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Kruskal with Naive Union-Find (Baseline)
1Hint 1Explore hintHide hint
Sort the edges, then for each edge decide if its endpoints are already in the same component. How do you answer 'same component?' without optimizations?
2Hint 2Explore hintHide hint
Keep a parent array. find(x) walks parent pointers up to the root; union(a, b) points one root at the other.
3Hint 3Explore hintHide hint
Without balancing, the trees can degenerate into chains, making find walk O(V) nodes — correct, but slow.
A · Core idea
The greedy skeleton of Kruskal is independent of how fast Union-Find is, so it helps to first nail the correctness with a simple Union-Find, then optimize.
The greedy and why it is correct (cut property). Sort edges ascending and walk them. For each edge (u, v, w), if u and v are in different components, taking this edge is safe: it is the lightest edge crossing the cut that separates u's component from the rest, and the cut property guarantees the lightest edge across any cut belongs to some MST. If they are already in the same component, adding the edge would create a cycle, so skip it.
The naive Union-Find. A parent[] array represents a forest. find(x) follows parent pointers until it reaches a root (a node that is its own parent). union(a, b) sets the root of one to the root of the other. 'Same component?' is just find(u) == find(v).
Why this version is slow. Without balancing, union can repeatedly attach a tree under a single node, building a long chain. Then find degrades to walking O(V) parent pointers. Across E edges that is up to O(E·V) — correct answers, poor performance. The fix in the optimal approach is two small changes (path compression and union by rank) that flatten these trees to near-constant height.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,1],[1,2,2],[0,2,3]]Array state
init
each node its own root
3C · Code with teaching comments
Reference implementation previewpublic int kruskalNaive(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); int[] parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; long total = 0;Explore the full codeHide the full code
D · Why it works and complexityO(E log E + E·V) timeO(V) spaceOpen the invariant and proofExplore the proofHide the proof
Separate correctness from performance: the greedy edge selection is already optimal: the only question is how fast you can answer 'are these two already connected?'. That is purely a Union-Find engineering choice.
ComplexityO(E log E + E·V) time, O(V) space — Sorting is O(E log E). Each find can be O(V) if the union trees degenerate into long chains, giving up to O(E·V) for the unioning phase.
E · Edge cases and pitfalls3find without path compression degrades to O(V) on long chains.Explore edge casesHide edge cases
Pitfalls
- find without path compression degrades to O(V) on long chains.
- Forgetting the V − 1 count check, so disconnected graphs return a wrong total.
- Comparing endpoints directly instead of their roots — misses cycles.
Approach 2 of 2 · Optimal
Kruskal with Path Compression + Union by Rank (Optimal)
1Hint 1Explore hintHide hint
The greedy is fixed; speed it up by making find nearly O(1). Two independent tricks do it.
2Hint 2Explore hintHide hint
Path compression: during find, point every node you pass directly at the root, flattening the tree for next time.
3Hint 3Explore hintHide hint
Union by rank: attach the shorter tree under the taller root so heights barely grow. Together they give near-constant amortized find/union (inverse-Ackermann).
A · Core idea
This is Kruskal as you would write it in an interview: the same greedy edge walk, backed by a Union-Find that is engineered to answer connectivity queries in essentially constant time.
The greedy, restated. Sort edges ascending by weight. For each (u, v, w), if find(u) != find(v) they are in different components, so adding the edge is safe (cut property) — union them, add w to the total, and increment the picked count. If they share a root, the edge would form a cycle, so skip it. Stop as soon as picked == V − 1; if you exhaust the edges before that, the graph is disconnected and no MST exists.
Path compression. When find(x) walks up to the root r, it then re-points every node along that path directly to r. The next find on any of those nodes is O(1). Implemented iteratively (two passes: find the root, then relink), there is no recursion, so a pathological input cannot overflow the call stack — important when V is 10⁵.
Union by rank. Each root carries a rank (an upper bound on its tree height). union(a, b) attaches the lower-rank root under the higher-rank root, so the combined tree's height does not grow. Only when both ranks are equal does the height increase by one, and the surviving root's rank is bumped. This keeps trees shallow before compression even kicks in.
Why the two together are so fast. Path compression flattens trees lazily during queries; union by rank keeps them shallow during merges. Combined, the amortized cost of m operations on n elements is O(m·α(n)), where α is the inverse Ackermann function — effectively a small constant (≤ 4) for any input that fits in memory. So the Union-Find phase is effectively linear, and the O(E log E) sort dominates the runtime.
Why an edge list, not an adjacency list. Kruskal processes edges globally in sorted order, so a flat list of (u, v, w) is the natural representation — no per-vertex adjacency needed. The whole algorithm is iterative loops over that list.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]Array state
(2,3,4)
add, total 4
19C · Code with teaching comments
D · Why it works and complexityO(E log E) timeO(V) spaceOpen the invariant and proofExplore the proofHide the proof
Kruskal cleanly factors into two reusable pieces: a greedy backed by the cut property, and a Union-Find that turns 'are these connected?' into a near-constant query. Path compression + union by rank is the canonical Union-Find you should be able to write from memory — it powers Number of Connected Components, Redundant Connection, and Accounts Merge too.
ComplexityO(E log E) time, O(V) space — Sorting dominates at O(E log E). With path compression + union by rank, the E find/union operations cost O(E·α(V)) ≈ O(E), where α is the inverse Ackermann function (≤ 4 for any realistic input).
E · Edge cases and pitfalls7single vertex, no edges (n=1) — V − 1 = 0 edges needed → total 0, already spanning.Explore edge casesHide edge cases
Edge cases handled
single vertex, no edges (n=1)V − 1 = 0 edges needed → total 0, already spanning.disconnected graphEdges exhaust with picked < V − 1 → return -1.parallel edges between same pairLighter one is taken first; the heavier becomes a skipped cycle edge.
Pitfalls
- Recursive find can stack-overflow on huge inputs — prefer the iterative two-pass form.
- Implementing only one of compression/rank — both matter for the near-O(1) bound.
- Forgetting to bump rank when ranks are equal — trees grow taller than necessary.
- Not returning -1 when fewer than V − 1 edges are picked (disconnected graph).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int kruskal(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); int[] parent = new int[n]; int[] rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Naive find without path compression
Long parent chains make each find O(V). Across E edges that approaches O(E·V), defeating the point of Union-Find.
Explore the code comparisonHide the code comparison
Naive find without path compression
Long parent chains make each find O(V). Across E edges that approaches O(E·V), defeating the point of Union-Find.
Don't write this
def find(x):
while parent[x] != x:
x = parent[x] # never flattens — stays slow
return xWrite this instead
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
parent[x], x = root, parent[x] # path compression
return root2Missing the disconnected-graph check
If the graph cannot be spanned, you must report it. Summing whatever edges you managed to pick returns a meaningless number.
Explore the code comparisonHide the code comparison
Missing the disconnected-graph check
If the graph cannot be spanned, you must report it. Summing whatever edges you managed to pick returns a meaningless number.
Don't write this
for (int[] e : edges) { if (union(...)) total += e[2]; }
return (int) total; // wrong when graph is disconnectedWrite this instead
for (int[] e : edges) { if (union(...)) { total += e[2]; picked++; } }
return picked == n - 1 ? (int) total : -1;3Comparing endpoints instead of roots
Two vertices can be in the same component without being equal. Only their roots reveal connectivity, so cycle detection must compare find(u) and find(v).
Explore the code comparisonHide the code comparison
Comparing endpoints instead of roots
Two vertices can be in the same component without being equal. Only their roots reveal connectivity, so cycle detection must compare find(u) and find(v).
Don't write this
if u != v: # wrong — they're rarely equal
union(u, v)Write this instead
if find(u) != find(v):
union(u, v)Revise
Carry the pattern into the interview
Pattern to remember
Sort edges + Union-Find cycle check (greedy)
Code pattern to memorize
sort edges by weight ascending
for (u, v, w) in edges:
if find(u) != find(v): # different components
union(u, v)
total += w; picked++
if picked == V - 1: breakRules to remember
- 1Sort edges ascending by weight, then greedily take the lightest that does not create a cycle.
- 2Use Union-Find with path compression + union by rank for near-constant
find/union. - 3An MST has exactly V − 1 edges — stop early once you've picked that many.
- 4If you finish the edges with fewer than V − 1 picks, the graph is disconnected (no spanning tree).
- 5
find(u) == find(v)before union means the edge would close a cycle — skip it.
Use this pattern when
- Minimum spanning tree / minimum cost to connect all nodes
- Edges are given as a list and the graph is **sparse** (E close to V)
- You can sort edges globally — no need to grow from a fixed start vertex
- Cycle detection across a stream of unioning operations
Choose another pattern when
- Dense graph (E ≈ V²) → Prim's with a heap is often better
- You need shortest paths, not a spanning tree → Dijkstra/Bellman-Ford
- Edges arrive sorted-by-source, not globally → Prim's grows locally
- Directed graph → MST is for undirected graphs; you want an arborescence instead
Interview takeaway
Kruskal is the global-greedy MST: sort every edge once, then let Union-Find arbitrate cycles. Master path compression and union by rank here — they recur in connected-components, account-merging, and redundant-connection problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical sort-then-Union-Find MST. Reach for it on minimum-spanning-tree problems with a global edge list, especially sparse graphs. The path-compression + union-by-rank Union-Find is the reusable core behind Number of Connected Components, Redundant Connection, and Accounts Merge.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Prim's Minimum Spanning TreeGrows the MST from one vertex using a min-heap; better on dense graphs.
- Min Cost to Connect All PointsComing soonMST on a complete graph of points with Manhattan-distance edges — Kruskal or Prim.
- Number of Connected ComponentsComing soonPure Union-Find — count distinct roots after unioning all edges.
- Redundant ConnectionComing soonUnion-Find cycle detection — the first edge whose endpoints already share a root is the redundant one.