Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Grow a minimum spanning tree outward from any one vertex. Keep a min-heap of edges crossing from the tree to the outside; repeatedly pull the cheapest such edge whose far end is not yet in the tree, add that vertex, and push its new outgoing edges. O((V + E) log V) with a binary heap.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can grow an MST greedily with a min-heap, articulate the difference from Dijkstra (edge weight vs path sum), and handle stale heap entries and disconnection.
Where candidates slip
Pushing accumulated path cost like Dijkstra instead of the single edge weight, or revisiting vertices already in the tree.
How to stand out
State the cut property that makes the lightest crossing edge safe, contrast Prim with Kruskal on density, and explain why any start vertex yields the same total.
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 previewNeed an MSTGraph dense or sparse?Dense, adjacency listSparse, edge listExplore the full treeCollapse the tree
How to read it:Order absorbed: 0, then 3 (edge 5), then 2 (edge 4), then 1 (edge 10). Total 19.
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
Prim with O(V²) Scan (Baseline)
1Hint 1Explore hintHide hint
Keep a key[] array: key[v] = weight of the cheapest known edge connecting v to the current tree. Start key[start]=0, rest infinity.
2Hint 2Explore hintHide hint
Each step, scan all vertices to find the not-yet-in-tree vertex with the smallest key. Add it, then update its neighbors' keys.
3Hint 3Explore hintHide hint
No heap needed — the linear scan is the bottleneck at O(V) per step, O(V²) total. For a complete graph that is as good as it gets.
A · Core idea
Before reaching for a heap, the simplest correct Prim keeps the frontier in a flat key[] array and finds the minimum by scanning.
The state. key[v] holds the weight of the cheapest edge currently known to connect vertex v to the growing tree (infinity if none yet). inTree[v] marks membership. Initialize key[start] = 0 so the start is pulled first.
Each step. Scan all vertices, pick the one with the smallest key that is not yet in the tree, add it (and add its key to the total), then relax: for each neighbor v not in the tree, if the connecting edge weight is smaller than key[v], lower key[v]. Repeat V times.
Why the greedy is correct (cut property). At every step the set of in-tree vertices forms one side of a cut. The vertex with the minimum key is reached by the lightest edge crossing that cut, and the cut property says the lightest crossing edge is always part of some MST. So pulling it is always safe.
Cost and when it wins. The O(V) minimum scan, done V times, gives O(V²). That sounds slow, but on a complete or near-complete graph where E ≈ V², the heap version's O(E log V) = O(V² log V) is actually worse — so the plain array Prim is the right call for very dense graphs. For sparse graphs, the heap version below is faster.
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]], start = 0Array state
after adding 0
relax to 1 and 2
3C · Code with teaching comments
Reference implementation previewpublic int primDense(int n, int[][] edges) { long[][] w = new long[n][n]; for (long[] row : w) Arrays.fill(row, Long.MAX_VALUE); for (int[] e : edges) { w[e[0]][e[1]] = Math.min(w[e[0]][e[1]], e[2]);Explore the full codeHide the full code
D · Why it works and complexityO(V²) timeO(V²) spaceOpen the invariant and proofExplore the proofHide the proof
The array-scan and heap versions are the same algorithm with different frontier data structures. Choosing between them is a density decision: dense favors the O(V²) scan, sparse favors the O((V+E) log V) heap.
ComplexityO(V²) time, O(V²) space — V iterations, each doing an O(V) scan for the minimum key plus O(V) neighbor updates → O(V²). On a dense graph (E ≈ V²) this ties the heap version; on sparse graphs the heap wins.
E · Edge cases and pitfalls3Using the dense V² version on a sparse graph where a heap is much faster.Explore edge casesHide edge cases
Pitfalls
- Using the dense V² version on a sparse graph where a heap is much faster.
- The adjacency matrix needs O(V²) memory — infeasible when V is large.
- Forgetting the disconnection check (key[u] still infinity).
Approach 2 of 2 · Optimal
Prim with Min-Heap (Optimal for Sparse/Moderate)
1Hint 1Explore hintHide hint
Replace the O(V) minimum scan with a min-heap so getting the cheapest crossing edge is O(log V).
2Hint 2Explore hintHide hint
Push (weight, vertex) for crossing edges. Pop the smallest; if the vertex is already in the tree, it is a stale entry — skip it.
3Hint 3Explore hintHide hint
When you add a vertex, push its outgoing edges (edge weight, neighbor) for neighbors not yet in the tree. Add the popped weight to the total.
A · Core idea
This is Prim as you would write it in an interview: the same grow-from-a-vertex greedy, but the frontier of crossing edges lives in a min-heap so the cheapest one is always O(log V) away.
The loop. Start by pushing (0, start) and marking nothing yet. Repeatedly pop the minimum-weight entry (w, u). If u is already in the tree, this is a stale crossing edge — discard it in O(1). Otherwise add u to the tree, add w to the running total, and for each neighbor v of u not yet in the tree, push (weight(u, v), v). When the tree holds all V vertices, the total is the MST weight.
The key difference from Dijkstra — and why it matters. Both algorithms run an identical min-heap relaxation loop, but the key differs. Dijkstra pushes the accumulated path cost from the source (dist[u] + w); Prim pushes only the single edge weight w that crosses into the tree. That is because an MST cares about the cost of connecting a vertex, not the distance traveled to reach it. Push dist[u] + w by mistake and you compute a shortest-path tree, not a minimum spanning tree — a classic interview trap.
Why we skip stale entries. As with Dijkstra, we push duplicates rather than doing decrease-key. A vertex can sit in the heap under several crossing-edge weights; the first time it is popped it comes with its cheapest crossing edge, so we take that and ignore the rest via an inTree check.
Why an adjacency list and an iterative loop. Neighbors are stored as an adjacency list (each undirected edge added in both directions), so absorbing a vertex only scans its real edges — giving the O(E) push bound. The main loop is a while over the heap, fully iterative, so there is no recursion and no stack-overflow risk even at V = 10⁵.
Correctness (cut property again). The in-tree set is one side of a cut, and the heap's minimum is the lightest edge crossing that cut to a new vertex. The cut property guarantees that edge belongs to some MST, so each greedy pull is safe. If the heap empties before the tree is full, the remaining vertices are unreachable — the graph is disconnected and no MST exists.
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]], start = 0Array state
pull 0 (w=0)
tree {0}
19C · Code with teaching comments
D · Why it works and complexityO((V + E) log V) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Prim and Dijkstra are the same min-heap machine with one knob changed: relax on edge weight (Prim) versus path sum (Dijkstra). Internalizing that single distinction lets you derive either algorithm from the other and instantly spot the wrong-key bug.
ComplexityO((V + E) log V) time, O(V + E) space — Each edge can be pushed once → O(E) pushes at O(log V) each. Each vertex is finalized once on pop. Total O((V + E) log V). Space is the adjacency list O(V + E) plus the heap.
E · Edge cases and pitfalls7single vertex (n=1) — Pop the start, count becomes 1 = V → total 0.Explore edge casesHide edge cases
Edge cases handled
single vertex (n=1)Pop the start, count becomes 1 = V → total 0.disconnected graphHeap empties with count < V → return -1.parallel edgesThe lighter is popped first; the heavier becomes a stale skip.
Pitfalls
- Pushing accumulated path cost (Dijkstra) instead of the single edge weight — builds a shortest-path tree, not an MST.
- Forgetting the inTree stale-skip, re-adding vertices and corrupting the total.
- Not adding edges in both directions for an undirected graph.
- Missing the count == V disconnection check, returning a partial total.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int prim(int n, int[][] edges) { List<int[]>[] adj = new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); for (int[] e : edges) { adj[e[0]].add(new int[]{e[1], e[2]});Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Using path sum instead of edge weight
Prim minimizes the cost to connect each vertex, which is a single edge weight. Adding the accumulated distance from the start (Dijkstra's relaxation) produces a shortest-path tree, not a minimum spanning tree.
Explore the code comparisonHide the code comparison
Using path sum instead of edge weight
Prim minimizes the cost to connect each vertex, which is a single edge weight. Adding the accumulated distance from the start (Dijkstra's relaxation) produces a shortest-path tree, not a minimum spanning tree.
Don't write this
for v, weight in adj[u]:
heapq.heappush(heap, (total + weight, v)) # path sum — WRONG for MSTWrite this instead
for v, weight in adj[u]:
if not in_tree[v]:
heapq.heappush(heap, (weight, v)) # single crossing-edge weight2No stale-entry skip
Because duplicates are pushed instead of decrease-key, a vertex may appear multiple times. Without the inTree check you add it more than once, inflating the total.
Explore the code comparisonHide the code comparison
No stale-entry skip
Because duplicates are pushed instead of decrease-key, a vertex may appear multiple times. Without the inTree check you add it more than once, inflating the total.
Don't write this
long[] top = heap.poll();
int u = (int) top[1];
inTree[u] = true;
total += top[0]; // may double-count uWrite this instead
long[] top = heap.poll();
int u = (int) top[1];
if (inTree[u]) continue; // skip stale
inTree[u] = true;
total += top[0];3Directed adjacency for an undirected MST
If you only add edge u→v, the tree can never grow back from v to u's side, so it may miss the cheapest connection and even falsely report disconnection.
Explore the code comparisonHide the code comparison
Directed adjacency for an undirected MST
If you only add edge u→v, the tree can never grow back from v to u's side, so it may miss the cheapest connection and even falsely report disconnection.
Don't write this
for u, v, w in edges:
adj[u].append((v, w)) # one direction onlyWrite this instead
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w)) # both directionsRevise
Carry the pattern into the interview
Pattern to remember
Grow the tree, min-heap of crossing edges (greedy)
Code pattern to memorize
push (0, start) ; total = 0
while heap and tree not full:
(w, u) = pop-min
if u in tree: continue # stale / already added
add u to tree ; total += w
for (v, weight) in adj[u]:
if v not in tree: push (weight, v)Rules to remember
- 1Skip a popped vertex already in the tree — the heap holds stale crossing edges.
- 2Add the edge weight to the total at the moment you pull the vertex in, not when you push it.
- 3Build an adjacency list; for undirected MST add each edge in both directions.
- 4If the loop ends with fewer than V vertices in the tree, the graph is disconnected → no MST.
- 5Any start vertex works — the MST total is the same regardless of where you begin.
Use this pattern when
- Minimum spanning tree on a **dense** graph (E close to V²)
- Graph is given as an adjacency list and you can grow from a start vertex
- You want to reuse the same min-heap relaxation skeleton as Dijkstra
- Minimum cost to connect all nodes where edges are easy to expand locally
Choose another pattern when
- Sparse graph with a global edge list → Kruskal's sort is simpler
- You need shortest paths, not a spanning tree → Dijkstra (note: Prim relaxes edge weight, Dijkstra relaxes path sum)
- Edges only available in a sorted stream → Kruskal
- Directed graph → MST is undirected; use a minimum arborescence instead
Interview takeaway
Prim is Dijkstra's twin: same min-heap loop, but the key is the single crossing-edge weight, not the accumulated path cost. It grows one connected tree; Kruskal merges many. Know both and pick by density.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical grow-the-tree MST with a min-heap. Reach for it on minimum-spanning-tree problems given an adjacency list, especially denser graphs. It shares its skeleton with Dijkstra (swap edge weight for path sum) and solves Min Cost to Connect All Points and water-distribution variants.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kruskal's Minimum Spanning TreeSort edges + Union-Find; better on sparse graphs with a global edge list.
- Min Cost to Connect All PointsComing soonDense complete graph of points — Prim's heap (or the O(V²) scan) is a great fit.
- Dijkstra's Shortest PathSame heap loop, but relax on path sum instead of edge weight.
- Optimize Water Distribution in a VillageComing soonAdd a virtual node for wells, then run Prim/Kruskal for the MST.