Kruskal's MST with Union-Find

Reported in interviews at Jump Trading Two Sigma

Problem statement

You have a connected, weighted, undirected graph with $n$ vertices labelled $0 \dots n-1$ and a list of edges. Each edge is given as $[u, v, w]$: an undirected edge between vertices $u$ and $v$ with weight $w$.

Implement mst_weight(n, edges) returning the total weight of a minimum spanning tree (MST), computed with Kruskal's algorithm backed by a union-find (disjoint-set) structure using path compression and union-by-rank. The total MST weight is unique even when the specific set of chosen edges is not.

Example

mst_weight(4, [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4]])  ->  6

The three cheapest edges (weights 1, 2, 3) connect all four vertices without forming a cycle; the weight-4 edge would close a cycle and is skipped, so the MST weight is $1 + 2 + 3 = 6$.

Going deeper (discussion):

  1. Prove Kruskal's is correct using the cut property.
  2. Show the running time is $O(m \log n)$.
  3. Compare with Prim's algorithm: when are binary-heap or Fibonacci-heap variants of Prim's preferable, and vice versa?
Show hint

Which data structure lets you ask, in near-constant time, whether two vertices are already connected by the edges you have kept so far?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems