Minimum Spanning Tree — Solution in Python, Java & C++
Minimum Spanning Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Spanning Tree is a medium coding problem on greedy, graph and union find, asked in Amazon, Flipkart and Samsung interviews.
- Difficulty: Medium
- Topics: Greedy, Graph, Union Find, Minimum Spanning Tree
- Asked at: Amazon, Flipkart, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a connected, undirected, weighted graph with n vertices numbered 0 to n - 1. Each edges[i] = [u, v, w] is an edge between u and v of weight w.
A spanning tree is a set of n - 1 edges that connects all the vertices. Return the sum of the weights of a minimum spanning tree — the smallest total weight any spanning tree can have.
Example 1
Input: n = 3, edges = [[0,1,5],[1,2,3],[0,2,1]]
Output: 4
Explanation: Keep the edges of weight 1 (0–2) and 3 (1–2); together they connect all three vertices.
Example 2
Input: n = 2, edges = [[0,1,5]]
Output: 5
Example 3
Input: n = 4, edges = [[0,1,2],[1,2,2],[2,3,2],[0,3,2],[0,2,5]]
Output: 6
Explanation: Any three of the four weight-2 edges form a spanning tree.
Constraints
2 <= n <= 1000n - 1 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i].length == 30 <= u, v < n, u != v1 <= w <= 1000there are no repeated edges, and the graph is connected
Hints for Minimum Spanning Tree
Hint 1
Sort the edges by weight. The lightest edge of the whole graph always belongs to some minimum spanning tree.
Hint 2
Walk the sorted edges and keep an edge only when it joins two vertices that are not yet connected; otherwise it would close a cycle.
Hint 3
A disjoint-set union (union–find) answers "are these already connected?" in near-constant time. Stop after
n - 1edges are kept.
How to solve Minimum Spanning Tree
Kruskal's algorithm: consider edges from lightest to heaviest and take every edge that connects two different components. The cut property guarantees each such edge is safe.
Approach
- Sort the edges by weight.
- Start a union–find structure with every vertex in its own set.
- For each edge
(u, v, w)in order: iffind(u) != find(v), union them and addwto the total. - Return the total once
n - 1edges have been taken (the graph is connected, so this always happens).
Why it works
When Kruskal takes edge e, it is the lightest edge crossing the cut between u's current component and the rest of the graph — every lighter edge was already examined and either taken or found to lie inside a component. The cut property says some minimum spanning tree contains the lightest edge across any cut, so each choice can be extended to an optimal tree. Skipped edges would close a cycle and are never needed.
Complexity
- Time —
O(E log E) - Space —
O(n + E)
Pitfalls
- Without path compression (or union by size) the union–find can degrade to linear time per query.
- Edges are undirected:
[u, v, w]connects both ways, so do not build a one-directional adjacency for Prim. - Equal weights are fine in any order — the total of a minimum spanning tree is unique even when the tree is not.
Reference solution
Python
from typing import List
def spanningTree(n: int, edges: List[List[int]]) -> int:
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0
taken = 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
total += w
taken += 1
if taken == n - 1:
break
return totalJava
public static int spanningTree(int n, int[][] edges) {
int[][] sorted = edges.clone();
Arrays.sort(sorted, (a, b) -> a[2] - b[2]);
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int total = 0, taken = 0;
for (int[] e : sorted) {
if (taken == n - 1) break;
int ru = mstFind(parent, e[0]), rv = mstFind(parent, e[1]);
if (ru != rv) { parent[ru] = rv; total += e[2]; taken++; }
}
return total;
}
static int mstFind(int[] parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}C++
static int mstFind(vector<int>& parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
int spanningTree(int n, vector<vector<int>>& edges) {
vector<vector<int>> sorted = edges;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
int total = 0, taken = 0;
for (auto& e : sorted) {
if (taken == n - 1) break;
int ru = mstFind(parent, e[0]), rv = mstFind(parent, e[1]);
if (ru != rv) { parent[ru] = rv; total += e[2]; taken++; }
}
return total;
}JavaScript
var spanningTree = function(n, edges) {
var parent = [];
for (var i = 0; i < n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
var sorted = edges.slice().sort(function(a, b) { return a[2] - b[2]; });
var total = 0, taken = 0;
for (var k = 0; k < sorted.length && taken < n - 1; k++) {
var ru = find(sorted[k][0]), rv = find(sorted[k][1]);
if (ru !== rv) { parent[ru] = rv; total += sorted[k][2]; taken++; }
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 264 greedy problems · the whole catalogue
Learn the technique: Greedy Algorithms · Graph Data Structure