Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the total weight of a Minimum Spanning Tree. Kruskal's greedy: sort all edges by weight ascending, then walk them cheapest-first, adding an edge only if its two endpoints are in different components (otherwise it would form a cycle). A union-find (disjoint set union) with path compression and union by rank tests 'same component?' and merges in near-O(1). Stop after n − 1 edges; sum their weights. O(E log E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for Kruskal + union-find on an MST question, can justify the greedy 'cheapest safe edge' choice, and implement disjoint-set union with path compression and union by rank correctly.
Where candidates slip
Adding an edge without checking for a cycle (forming loops), writing a find without path compression (degrading to O(n) per query), or summing all edges instead of stopping at n − 1.
How to stand out
State the cut property that justifies the greedy choice, contrast Kruskal (edge-centric, sort) with Prim (vertex-centric, heap), and mention path compression + union by rank give the inverse-Ackermann amortized bound.
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 approachFirst decision previewMinimum spanning tree?Input shape?Edge list, sparseDense / adjacency, start nodeExplore the full treeCollapse the tree
How to read it:Green edges (1, 99, 100) form the MST; the 150 and 200 edges would close cycles.
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 Label-Relabel DSU (Baseline)
1Hint 1Explore hintHide hint
The greedy is the same: sort edges, take an edge only if it joins two different pieces. The only question is how to test 'same piece?' cheaply.
2Hint 2Explore hintHide hint
Simplest idea: give every node a component label. Two nodes are in the same piece iff they share a label. To merge, pick one label and overwrite every node carrying the other.
3Hint 3Explore hintHide hint
Relabeling scans all V nodes, so each accepted edge costs O(V). With up to n − 1 merges that's O(V²) on top of the sort. Correct, but slow — it motivates union-find.
A · Core idea
Kruskal's logic doesn't need a fancy structure to be correct — only a way to ask 'are u and v already connected?'.
The component-label idea. Give node i an initial label comp[i] = i. Two nodes are in the same component iff comp[u] == comp[v]. Sort the edges ascending. For each (u, v, w): if the labels differ, accept the edge (total += w) and merge by rewriting every node whose label equals comp[v] to comp[u]. If the labels already match, the edge would close a cycle — skip it.
Why it's correct. It implements Kruskal exactly: edges are considered cheapest-first, and an edge is accepted iff it connects two distinct components. The cut property guarantees each such accepted edge is safe (belongs to some MST), so the accumulated total is the true minimum.
Why we don't ship it. The merge scans all V nodes to relabel, so a graph that needs V − 1 merges does Θ(V²) relabeling work. At n = 3000 that's ~9 × 10⁶ in the worst case — survivable here, but it scales badly. Replacing the relabel with union-find's tree-of-parents drops each operation to near-O(1).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2,1],[3,2,150],[4,3,99],[1,4,100],[3,1,200]]Array state
init
each node its own label
200C · Code with teaching comments
Reference implementation previewpublic int kruskals(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); int[] comp = new int[n + 1]; for (int i = 1; i <= n; i++) comp[i] = i; int total = 0, used = 0;Explore the full codeHide the full code
D · Why it works and complexityO(E log E + V·E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
The greedy edge selection is the soul of Kruskal; the disjoint-set data structure only accelerates the 'same component?' test. Starting from label-relabel makes that separation explicit — and shows exactly what union-find optimizes.
ComplexityO(E log E + V·E) time, O(V + E) space — Sorting edges is O(E log E). Each merge relabels by scanning all V nodes → O(V) per merge, and there are up to V − 1 merges → O(V²) = O(V·E) in the worst dense case. Membership tests are O(1) (compare labels). Total is dominated by the relabeling when the graph is dense.
E · Edge cases and pitfalls3Forgetting to sort the edges — the greedy is only correct cheapest-first.Explore edge casesHide edge cases
Pitfalls
- Forgetting to sort the edges — the greedy is only correct cheapest-first.
- Relabeling the wrong direction is harmless, but rescanning all nodes per merge is the O(V²) cost.
- Not stopping at n − 1 edges (harmless for the total but wasteful).
Approach 2 of 2 · Optimal
Kruskal with Union-Find (Optimal)
1Hint 1Explore hintHide hint
The label-relabel merge is slow because it touches every node. Can you represent each component as a tree of parent pointers so merging is just re-pointing one root at another?
2Hint 2Explore hintHide hint
Union-find: find(x) follows parent pointers to the root (the component id); union(a, b) links one root under the other. Path compression flattens the tree during find; union by rank keeps it shallow.
3Hint 3Explore hintHide hint
With both optimizations, find/union run in inverse-Ackermann amortized time (effectively O(1)). The sort then dominates → O(E log E).
A · Core idea
Union-find replaces the O(V) relabel with an O(1)-amortized pointer operation, keeping Kruskal's greedy identical.
The structure. Each component is a rooted tree of parent[] pointers; the root is the component's representative. find(x) walks to the root, and path compression re-points every node on the way directly to the root, flattening future lookups. union(a, b) finds both roots and, by union by rank, hangs the shorter tree under the taller so depth grows logarithmically at worst — and effectively stays constant with compression.
The Kruskal loop. Sort edges ascending. For each (u, v, w): if find(u) != find(v), the endpoints are in different components, so the edge is safe — union(u, v), add w to the total, and increment the count of used edges. If the roots match, the edge would create a cycle, so skip it. Stop once n − 1 edges are accepted.
Why it's correct. The cut property: for any partition of the vertices into two sets, the minimum-weight edge crossing it belongs to some MST. Processing edges in increasing weight, the first edge that joins two distinct components is exactly such a minimum crossing edge for the cut separating one component from the rest — so adding it is always safe. Skipping cycle edges keeps the result acyclic, and after n − 1 safe edges every node is connected: a minimum spanning tree.
Why it's fast. The only non-trivial cost is sorting; the connectivity bookkeeping is near-linear. That is why Kruskal is the go-to MST algorithm on sparse, edge-list graphs.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2,1],[3,2,150],[4,3,99],[1,4,100],[3,1,200]]Array state
init
every node is its own root
200C · Code with teaching comments
D · Why it works and complexityO(E log E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Union-find is the data structure that makes incremental connectivity cheap: 'are these two already connected, and if not, connect them' in amortized constant time. Path compression + union by rank together give the famous inverse-Ackermann bound. Kruskal is its showcase application, but the same DSU powers cycle detection, friend-circle merging, and Number of Connected Components.
ComplexityO(E log E) time, O(V + E) space — Sorting is O(E log E). Each edge triggers two finds and at most one union; with path compression and union by rank these are O(α(V)) amortized (α is the inverse Ackermann function, ≤ 4 for any practical n). So the union-find work is O(E·α(V)), dwarfed by the sort. Total O(E log E). Space is O(V) for parent/rank arrays plus O(E) for edges.
E · Edge cases and pitfalls7parallel edges [1,2,5] and [1,2,2] — Sorted, the weight-2 edge unions 1 and 2 first; the weight-5 edge later finds equal roots and is skipped.Explore edge casesHide edge cases
Edge cases handled
parallel edges [1,2,5] and [1,2,2]Sorted, the weight-2 edge unions 1 and 2 first; the weight-5 edge later finds equal roots and is skipped.self-loop [u, u, w]find(u) == find(u) always → union returns false → always skipped, never affecting the total.minimum tree (n = 2, one edge)The single edge unions the two nodes; used reaches n − 1 = 1 and the loop stops with total = that weight.
Pitfalls
- Omitting path compression and/or union by rank — find degrades toward O(n), risking a TLE.
- Adding an edge before the find check — creates cycles and overcounts the weight.
- Summing every edge instead of only the n − 1 accepted ones.
- Off-by-one in 1-indexed vs 0-indexed parent arrays.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewprivate int[] parent, rank_; public int kruskals(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); parent = new int[n + 1];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Skipping the cycle check
Kruskal must reject any edge whose endpoints are already connected. Adding it creates a cycle and inflates the total beyond the MST weight.
Explore the code comparisonHide the code comparison
Skipping the cycle check
Kruskal must reject any edge whose endpoints are already connected. Adding it creates a cycle and inflates the total beyond the MST weight.
Don't write this
for u, v, w in sorted_edges:
union(u, v) # always merges — cycles included
total += wWrite this instead
for u, v, w in sorted_edges:
if find(u) != find(v): # only safe (non-cycle) edges
union(u, v)
total += w2find without path compression
A naive find walks parent pointers to the root every time. Without compression the trees can grow linear in depth, making each query O(n) and the whole solution slow on large sparse graphs.
Explore the code comparisonHide the code comparison
find without path compression
A naive find walks parent pointers to the root every time. Without compression the trees can grow linear in depth, making each query O(n) and the whole solution slow on large sparse graphs.
Don't write this
private int find(int x) {
while (parent[x] != x) x = parent[x]; // no compression
return x;
}Write this instead
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}3Forgetting to sort
The greedy correctness relies on examining the cheapest remaining edge each step. Processing edges in input order can pick a heavier edge over a lighter safe one, producing a non-minimal tree.
Explore the code comparisonHide the code comparison
Forgetting to sort
The greedy correctness relies on examining the cheapest remaining edge each step. Processing edges in input order can pick a heavier edge over a lighter safe one, producing a non-minimal tree.
Don't write this
for u, v, w in edges: # original order
if find(u) != find(v): ...Write this instead
edges.sort(key=lambda e: e[2]) # ascending by weight
for u, v, w in edges:
if find(u) != find(v): ...Revise
Carry the pattern into the interview
Pattern to remember
Greedy cheapest-edge + union-find cycle check
Code pattern to memorize
sort edges by weight ascending
parent[i] = i (each node its own set)
total = 0, used = 0
for (u, v, w) in sorted edges:
if find(u) != find(v): # different components → no cycle
union(u, v)
total += w
used += 1
if used == n - 1: break
return totalRules to remember
- 1Sort edges ascending by weight — Kruskal's greedy correctness depends on always considering the cheapest remaining edge.
- 2Add an edge only if its endpoints are in different sets; same-set means a cycle, so skip it.
- 3Use union-find with path compression + union by rank/size for near-O(1)
find/union. - 4A spanning tree has exactly n − 1 edges — stop early once you've added that many.
- 5On a tie in weight, either edge is fine; the total MST weight is unique even if the tree itself isn't.
Use this pattern when
- Minimum (or maximum) spanning tree of a connected, undirected, weighted graph
- Edge list is the natural input and the graph may be **sparse**
- You can afford to **sort all edges** once up front
- You need cycle detection across incremental unions → union-find
Choose another pattern when
- Graph given as an adjacency matrix / dense and you start from a node → Prim's with a heap may be cleaner
- You need shortest *paths*, not a spanning tree → Dijkstra/Bellman-Ford (MST ≠ shortest-path tree)
- Directed graph → MST is undefined; you want an arborescence (Chu–Liu/Edmonds)
- Graph is disconnected and a single tree is required → no MST exists (only a spanning forest)
Interview takeaway
Kruskal is the edge-centric MST: sort once, sweep cheapest-first, and let union-find veto any edge that would close a cycle. The disjoint-set structure is what makes the cycle test near-constant time, turning the whole algorithm into O(E log E) dominated by the sort.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Greedy MST via Kruskal + Union-Find. Recognize it on any 'cheapest way to connect everything' question over an undirected weighted graph given as an edge list. Sort edges, sweep cheapest-first, and let disjoint-set union veto cycles. Switch to Prim with a heap when the graph is dense or naturally given by adjacency from a start node.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Prim's (MST): Special SubtreeSame MST, vertex-centric: grow one tree from a start node, always pulling in the cheapest edge to a new vertex via a min-heap.
- Connecting Cities With Minimum CostComing soonDirect MST application; return -1 if the graph can't be fully connected (fewer than n − 1 edges accepted).
- Min Cost to Connect All PointsComing soonBuild a complete graph with Manhattan-distance edges, then run Kruskal or Prim for the MST.
- Number of Connected ComponentsThe same union-find without weights — count distinct roots after unioning all edges.