Minimum spanning tree

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four villages A, B, C, D need to be joined by roads so that you can drive from any village to any other, possibly through other villages. The possible roads and their costs: B–D 3, A–B 4, A–D 7, B–C 9, A–C 12, C–D 14. You want the cheapest set of roads that connects everyone.

By hand you would pick the cheapest road first, then the next cheapest that is still useful, and skip a road that only joins villages already connected. That instinct is right, but "already connected" is the hard part: with 4 villages you can see it; with 10,000 points and millions of candidate roads you need a fast way to answer "are these two already joined?"

Build the structure, one piece at a time

Piece one: a sorted list of roads, cheapest first: B–D 3, A–B 4, A–D 7, B–C 9, A–C 12, C–D 14. Sorting is the only expensive step.

Piece two: a way to track which villages are already joined. Use a union–find structure (its own pattern page explains it): each village starts as its own group, find tells you a village's group, union merges two groups. Start: {A} {B} {C} {D}.

Piece three, the one rule (Kruskal): go down the sorted list; take a road if its two ends are in different groups, and union them; skip it if they are already in the same group, because that road would only form a loop.

1. B–D 3: different groups, take it. Groups {A} {B,D} {C}. Cost 3.
2. A–B 4: different groups, take it. Groups {A,B,D} {C}. Cost 7.
3. A–D 7: A and D are already together, skip.
4. B–C 9: different groups, take it. Groups {A,B,C,D}. Cost 16.

Three roads join four villages, and a tree on n nodes always has exactly n − 1 edges, so we can stop. Total 16.

Prim's method reaches the same tree from the other direction: start at one village, keep a min-heap of roads leaving the villages you have so far, and always add the cheapest road that reaches a new village.

Why it is correct

The invariant: the roads chosen so far all belong to some cheapest possible connecting tree. The key fact is the cut property: split the villages into any two non-empty sides; the cheapest road crossing between the sides is safe to take. Suppose a cheapest tree did not use that road e. Adding e to that tree makes a loop, and the loop must cross between the two sides somewhere else on a road f. Then

cost(e) ≤ cost(f), so swapping f for e gives a tree that is no more expensive

Kruskal's next taken road is exactly the cheapest road crossing between "its group" and "everything else", so each step stays inside some cheapest tree.

Why it is fast

Sorting E roads costs E log E. The scan then does one or two union–find operations per road, each nearly constant:

work ≈ E log E + E · α(n) ≈ E log E

Prim with a binary heap is also E log V. For 10,000 points with all pairs as candidate roads, E is about 50 million, so sorting dominates and Prim with an array scan, V² = 100 million, is competitive.

How to recognise it in an interview

Cues: "connect all points with minimum total cost", "cheapest network", "every node reachable", costs on edges and no requirement about path lengths. The first thing to say: "this is a minimum spanning tree; sort the edges and union–find, or Prim from one node." Min Cost to Connect All Points is the example above with Manhattan distances as costs. Optimize Water Distribution in a Village adds a virtual node for "dig a well here", turning well costs into edges so the same routine applies.

02The idea in one line

Kruskal: sort edges, union-find to skip cycles. Prim: grow from one node with a heap.

Reach for it when: Min cost to connect points, water distribution, critical edges.

Cost: O(E log E) time.

03The walk-through, step by step

The video works one example: Min Cost to Connect 4 points. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort all 6 edges by weight; the MST needs n − 1 = 3 of them
2. B–D (3): joins two components, take it, cost 3
3. A–B (4): joins two components, take it, cost 7
4. A–D (7): both already connected, would form a cycle, skip
5. B–C (9): joins two components, take it, cost 16
6. 3 edges chosen: every point connected, total cost 16
7. Cut property: the lightest edge leaving a component is always safe
8. Sorting dominates: O(E log E); Prim with a heap is the same bound

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).