Minimum Spanning Tree

Medium
1680.

Minimum Spanning Tree

Minimum Spanning Tree is a medium coding problem on greedy, graph and union find, asked in Amazon, Flipkart and Samsung interviews.

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 <= 1000
  • n - 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= u, v < n, u != v
  • 1 <= w <= 1000
  • there are no repeated edges, and the graph is connected
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var spanningTree = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • n - 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= u, v < n, u != v
  • 1 <= w <= 1000
  • there are no repeated edges, and the graph is connected

Hints for Minimum Spanning Tree

  1. Hint 1

    Sort the edges by weight. The lightest edge of the whole graph always belongs to some minimum spanning tree.

  2. 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.

  3. Hint 3

    A disjoint-set union (union–find) answers "are these already connected?" in near-constant time. Stop after n - 1 edges 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

  1. Sort the edges by weight.
  2. Start a union–find structure with every vertex in its own set.
  3. For each edge (u, v, w) in order: if find(u) != find(v), union them and add w to the total.
  4. Return the total once n - 1 edges 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 total

Java

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