What is the brute force approach and complexity for Kruskal's Minimum Spanning Tree?

Test every set of V − 1 edges; keep the cheapest one that reaches all nodes with time complexity O(2^E · E) and space complexity O(V + E).

What is the optimal approach and complexity for Kruskal's Minimum Spanning Tree?

Sort by weight; keep an edge only if Union-Find says its ends are in different groups with optimal time complexity O(E log E) and space complexity O(V).

How do you identify the pattern for Kruskal's Minimum Spanning Tree?

Look for key signals in the prompt: "connect every node" indicates The answer is a connected set of edges: exactly V − 1 edges and no cycle.; "smallest possible total weight" indicates Minimum spanning tree: the cheapest connected set of edges.; "undirected weighted edges" indicates Sort the edges, then let Union-Find say whether an edge joins two groups..

Kruskal's Minimum Spanning Tree

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelUnion-Find + Kruskal (Minimum Spanning Tree)

Complexity:O(2^E · E)→O(E log E)

Key Insight

Sort the edges from cheapest to most expensive and walk through them. Keep an edge when its two ends are in different groups, and merge those groups. Skip an edge when both ends already share a group, because it would close a cycle. Stop after V − 1 kept edges.

Core Validity Invariant

An edge is safe to keep exactly when its two ends are in different groups. If they already share a group, keeping the edge would close a cycle, so it must be skipped.

Problem

You are given a connected, undirected graph with V nodes, numbered 0 to V − 1. Each edge [u, v, w] joins nodes u and v and has weight w.

Choose some edges so that every node is connected to every other node and the chosen edges contain no cycle. Such a set is a spanning tree. Return the smallest possible total weight of a spanning tree. That number is the minimum spanning tree (MST) weight.

Input

V, the number of nodes, and edges, a list of [u, v, w] triples.

Output

A single integer: the total weight of a minimum spanning tree.

Example 1

Input: V = 3, edges = [[0,1,5],[1,2,3],[0,2,1]]

Output: 4

Keeping 0–2 (1) and 1–2 (3) reaches all 3 nodes for a total of 4. The other two pairs of edges cost 8 and 6.

Example 2

Input: V = 2, edges = [[0,1,5]]

Output: 5

Only one edge can be kept, so the answer is its weight.

Example 3

Input: V = 6, edges = [[0,1,1],[1,2,2],[0,2,5],[3,4,3],[4,5,4],[3,5,6],[1,4,7],[2,3,9]]

Output: 17

There are two triangles, {0,1,2} and {3,4,5}, joined by bridges 1–4 (7) and 2–3 (9). Each triangle keeps its two cheapest edges (1 + 2 = 3 and 3 + 4 = 7), and the cheapest bridge 1–4 (7) joins them: 3 + 7 + 7 = 17.

Constraints

• The graph is connected and undirected.
• Nodes are numbered from 0 to V − 1.
• Each edge is [u, v, w]: it joins nodes u and v with weight w.
• 1 <= V <= 1000, 1 <= E <= V*(V-1)/2

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A spanning tree on V nodes has how many edges? Draw a small one and count.
2.
If I keep the single cheapest edge in the whole graph, can it ever be the wrong choice?
3.
When is keeping an edge a mistake? What does it do to the groups of nodes that are already connected?
4.
If every node keeps its own cheapest edge, do all the nodes end up connected to each other?
5.
I keep asking whether two nodes are already connected, while edges keep arriving. What structure answers that quickly?

Brute force approach

Idea

A spanning tree on V nodes has exactly V − 1 edges. So try every subset of the input edges, skip the subsets whose size is not V − 1, and check whether the rest reaches every node. The cheapest subset that passes is the answer.

Thinking process

1
The answer is a set of V − 1 edges, so only subsets of exactly that size need checking.
2
Example: V = 3 with edges 0–1 (5), 1–2 (3), 0–2 (1). The three 2-edge sets cost 8, 6 and 4. All three reach the 3 nodes, so the cheapest one, 4, is the answer.
3
The reach check matters. On 4 nodes, the 3-edge set 0–1, 1–2, 0–2 has the right size, but it forms a cycle and leaves node 3 unreached, so it is not a spanning tree and must be dropped.

Code & Implementation

brute.cpp

class Solution {
public:
    int spanningTree(int V, vector<vector<int>>& edges) {
        int E = edges.size();
        long long best = LLONG_MAX;

        // Try every subset of edges, written as a bit mask (bit i = edge i is picked).
        for (int mask = 0; mask < (1 << E); mask++) {
            // A spanning tree on V nodes has exactly V - 1 edges. Skip every other subset.
            if (__builtin_popcount(mask) != V - 1) continue;

            // Build the graph from the picked edges and walk it from node 0.
            vector<vector<int>> adj(V);
            long long cost = 0;
            for (int i = 0; i < E; i++) {
                if (!(mask >> i & 1)) continue;
                adj[edges[i][0]].push_back(edges[i][1]);
                adj[edges[i][1]].push_back(edges[i][0]);
                cost += edges[i][2];
            }
            vector<bool> seen(V, false);
            vector<int> stack = {0};
            seen[0] = true;
            int reached = 1;
            while (!stack.empty()) {
                int u = stack.back();
                stack.pop_back();
                for (int v : adj[u]) {
                    if (!seen[v]) {
                        seen[v] = true;
                        reached++;
                        stack.push_back(v);
                    }
                }
            }

            // V - 1 edges that reach every node form a tree, so keep the cheapest one.
            if (reached == V) best = min(best, cost);
        }
        return best == LLONG_MAX ? -1 : (int)best;
    }
};

import java.util.*;

class Solution {
    public int spanningTree(int V, int[][] edges) {
        int E = edges.length;
        long best = Long.MAX_VALUE;

        // Try every subset of edges, written as a bit mask (bit i = edge i is picked).
        for (int mask = 0; mask < (1 << E); mask++) {
            // A spanning tree on V nodes has exactly V - 1 edges. Skip every other subset.
            if (Integer.bitCount(mask) != V - 1) continue;

            // Build the graph from the picked edges and walk it from node 0.
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < V; i++) {
                adj.add(new ArrayList<>());
            }
            long cost = 0;
            for (int i = 0; i < E; i++) {
                if (((mask >> i) & 1) == 0) continue;
                adj.get(edges[i][0]).add(edges[i][1]);
                adj.get(edges[i][1]).add(edges[i][0]);
                cost += edges[i][2];
            }
            boolean[] seen = new boolean[V];
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(0);
            seen[0] = true;
            int reached = 1;
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : adj.get(u)) {
                    if (!seen[v]) {
                        seen[v] = true;
                        reached++;
                        stack.push(v);
                    }
                }
            }

            // V - 1 edges that reach every node form a tree, so keep the cheapest one.
            if (reached == V) best = Math.min(best, cost);
        }
        return best == Long.MAX_VALUE ? -1 : (int) best;
    }
}

from typing import List
import math

class Solution:
    def spanningTree(self, V: int, edges: List[List[int]]) -> int:
        E = len(edges)
        best = math.inf

        # Try every subset of edges, written as a bit mask (bit i = edge i is picked).
        for mask in range(1 << E):
            # A spanning tree on V nodes has exactly V - 1 edges. Skip every other subset.
            if bin(mask).count('1') != V - 1:
                continue

            # Build the graph from the picked edges and walk it from node 0.
            adj: List[List[int]] = [[] for _ in range(V)]
            cost = 0
            for i in range(E):
                if not ((mask >> i) & 1):
                    continue
                adj[edges[i][0]].append(edges[i][1])
                adj[edges[i][1]].append(edges[i][0])
                cost += edges[i][2]

            seen = [False] * V
            stack = [0]
            seen[0] = True
            reached = 1
            while stack:
                u = stack.pop()
                for v in adj[u]:
                    if not seen[v]:
                        seen[v] = True
                        reached += 1
                        stack.append(v)

            # V - 1 edges that reach every node form a tree, so keep the cheapest one.
            if reached == V:
                best = min(best, cost)

        return -1 if best == math.inf else int(best)

function popcount(x: number): number {
    let count = 0;
    while (x > 0) {
        count += x & 1;
        x >>>= 1;
    }
    return count;
}

export function spanningTree(V: number, edges: number[][]): number {
    const E = edges.length;
    let best = Infinity;

    // Try every subset of edges, written as a bit mask (bit i = edge i is picked).
    const limit = 1 << E;
    for (let mask = 0; mask < limit; mask++) {
        // A spanning tree on V nodes has exactly V - 1 edges. Skip every other subset.
        if (popcount(mask) !== V - 1) continue;

        // Build the graph from the picked edges and walk it from node 0.
        const adj: number[][] = Array.from({ length: V }, () => []);
        let cost = 0;
        for (let i = 0; i < E; i++) {
            if (!((mask >> i) & 1)) continue;
            adj[edges[i][0]].push(edges[i][1]);
            adj[edges[i][1]].push(edges[i][0]);
            cost += edges[i][2];
        }
        const seen: boolean[] = new Array(V).fill(false);
        const stack: number[] = [0];
        seen[0] = true;
        let reached = 1;
        while (stack.length > 0) {
            const u = stack.pop()!;
            for (const v of adj[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    reached++;
                    stack.push(v);
                }
            }
        }

        // V - 1 edges that reach every node form a tree, so keep the cheapest one.
        if (reached === V) best = Math.min(best, cost);
    }
    return best === Infinity ? -1 : best;
}

Complexity

Time O(2^E · E)Space O(V + E)

There are 2^E subsets of the E edges. Subsets of the wrong size are skipped at once. For each subset of size V − 1, a walk over the graph costs O(V + E). Fine for a handful of edges, hopeless for real inputs.

Optimized approach

Idea

Start from brute force

Brute force tries every set of V − 1 edges and then checks each one for reach and cost. Most of those sets are not even trees.

Find the repeated work

Brute force keeps building and checking sets that could never be the answer, such as sets with a cycle. Kruskal never builds such a set: it adds an edge only when that edge is safe.

Define the state — what variables do I need?

sorted edges: All edges, cheapest first. The loop moves forward once per edge.
dsu: The groups of nodes already connected by the edges kept so far.
total, used: The sum of the kept weights, and how many edges have been kept.

Define validity

An edge is safe to keep exactly when its two ends are in different groups. If they already share a group, keeping the edge would close a cycle, so it must be skipped.

Define the transitions — when does each pointer move, and why is it safe?

Each edge, in weight order

if dsu.unite(u, v) succeeds: total += w, used++

unite fails only when both ends already share a root, which is exactly the cycle case. Otherwise the edge merges two groups and is kept.

used == V − 1

stop the loop

A tree on V nodes has exactly V − 1 edges. Once we have that many, the kept edges already connect every node.

What does the current window add to the answer?

A kept edge adds its weight to total. A skipped edge adds nothing and changes no group.

Code & Implementation

optimal.cpp

// Union-Find (Disjoint Set Union) with path compression + union by size.
struct DSU {
    vector<int> parent, sz;
    int groups;
    DSU(int n) : parent(n), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);             // hang the smaller tree under the bigger one
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
};

class Solution {
public:
    int spanningTree(int V, vector<vector<int>>& edges) {
        // Kruskal: look at the cheapest edges first.
        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        DSU dsu(V);
        long long total = 0;
        int used = 0;
        for (auto& e : edges) {
            // Keep the edge only if its two ends are in different groups.
            // If they already share a group, the edge would close a cycle.
            if (!dsu.unite(e[0], e[1])) continue;
            total += e[2];
            // A spanning tree on V nodes has exactly V - 1 edges, so we can stop here.
            if (++used == V - 1) break;
        }
        return used == V - 1 ? (int)total : -1;
    }
};

import java.util.*;

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    int[] parent, sz;
    int groups;

    public DSU(int n) {
        parent = new int[n];
        sz = new int[n];
        groups = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    public int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    public boolean unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) {
            int tmp = a; a = b; b = tmp;             // hang the smaller tree under the bigger one
        }
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
}

class Solution {
    public int spanningTree(int V, int[][] edges) {
        // Kruskal: look at the cheapest edges first.
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

        DSU dsu = new DSU(V);
        long total = 0;
        int used = 0;
        for (int[] e : edges) {
            // Keep the edge only if its two ends are in different groups.
            // If they already share a group, the edge would close a cycle.
            if (!dsu.unite(e[0], e[1])) continue;
            total += e[2];
            // A spanning tree on V nodes has exactly V - 1 edges, so we can stop here.
            if (++used == V - 1) break;
        }
        return used == V - 1 ? (int) total : -1;
    }
}

from typing import List

# Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.groups = n

    def find(self, x: int) -> int:                              # the root that names x's group
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]         # path compression (halving): skip a level each step
            x = self.parent[x]
        return x

    def unite(self, a: int, b: int) -> bool:                     # false when a and b were already in one group
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a                                         # hang the smaller tree under the bigger one
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.groups -= 1
        return True

class Solution:
    def spanningTree(self, V: int, edges: List[List[int]]) -> int:
        # Kruskal: look at the cheapest edges first.
        edges.sort(key=lambda e: e[2])

        dsu = DSU(V)
        total = 0
        used = 0
        for e in edges:
            # Keep the edge only if its two ends are in different groups.
            # If they already share a group, the edge would close a cycle.
            if not dsu.unite(e[0], e[1]):
                continue
            total += e[2]
            # A spanning tree on V nodes has exactly V - 1 edges, so we can stop here.
            used += 1
            if used == V - 1:
                break
        return int(total) if used == V - 1 else -1

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    parent: number[];
    sz: number[];
    groups: number;

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.sz = new Array(n).fill(1);
        this.groups = n;
    }

    find(x: number): number {                              // the root that names x's group
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];  // path compression (halving): skip a level each step
            x = this.parent[x];
        }
        return x;
    }

    unite(a: number, b: number): boolean {                 // false when a and b were already in one group
        a = this.find(a);
        b = this.find(b);
        if (a === b) return false;
        if (this.sz[a] < this.sz[b]) {
            const tmp = a; a = b; b = tmp;                 // hang the smaller tree under the bigger one
        }
        this.parent[b] = a;
        this.sz[a] += this.sz[b];
        this.groups--;
        return true;
    }
}

export function spanningTree(V: number, edges: number[][]): number {
    // Kruskal: look at the cheapest edges first.
    edges.sort((a, b) => a[2] - b[2]);

    const dsu = new DSU(V);
    let total = 0;
    let used = 0;
    for (const e of edges) {
        // Keep the edge only if its two ends are in different groups.
        // If they already share a group, the edge would close a cycle.
        if (!dsu.unite(e[0], e[1])) continue;
        total += e[2];
        // A spanning tree on V nodes has exactly V - 1 edges, so we can stop here.
        if (++used === V - 1) break;
    }
    return used === V - 1 ? total : -1;
}

Complexity

Time O(E log E)Space O(V)

Sorting the E edges dominates, O(E log E). Each unite and find is almost O(1) with path compression and union by size. The sort runs in place, so the only extra memory is the DSU arrays, O(V).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Test every set of V − 1 edges; keep the cheapest one that reaches all nodes	O(2^E · E)	O(V + E)
Optimal	Sort by weight; keep an edge only if Union-Find says its ends are in different groups	O(E log E)	O(V)

Why does this belong to this pattern?

Clues in the problem statement

“connect every node”The answer is a connected set of edges: exactly V − 1 edges and no cycle.
“smallest possible total weight”Minimum spanning tree: the cheapest connected set of edges.
“undirected weighted edges”Sort the edges, then let Union-Find say whether an edge joins two groups.

Edges sorted by weight+keep an edge if its ends are in different groups+stop at V − 1 kept edges→Union-Find + Kruskal (Minimum Spanning Tree)

This is the anchor MST problem: sort the edges, and let Union-Find decide each one. The one rule to remember is same group means skip, because that edge would close a cycle. Later questions in this sub-pattern change where the edges come from (every pair of points, a list of cities), not this rule.

Don't make this mistake

Taking each node's cheapest edge (pattern confusion)

✗ // each node picks its own cheapest edge for (int u = 0; u < V; u++) total += cheapest[u];

✓ sort the edges by weight; keep an edge only if dsu.unite(u, v) succeeds

A node's cheapest edge is not a tree. On the walkthrough graph, nodes 0 and 1 both pick 0–1 (1), node 2 picks 1–2 (2), nodes 3 and 4 both pick 3–4 (3), and node 5 picks 4–5 (4). That is only 4 distinct edges with total 10, and it leaves two separate groups {0,1,2} and {3,4,5}. The bridges 1–4 (7) and 2–3 (9) are nobody's cheapest edge, so they are never taken. The answer is 17, not 10.

Sorting by the wrong key

✗ sort(edges.begin(), edges.end()); // compares u first, then v, then w

✓ sort by e[2] (the weight) only

Plain sort on [u, v, w] orders by the first node, not by weight. On the walkthrough graph, the edges then come in the order 0–1 (1), 0–2 (5), 1–2 (2), 1–4 (7), 2–3 (9), 3–4 (3), 3–5 (6), 4–5 (4). Kruskal keeps 0–1, 0–2, 1–4, 2–3 and 3–5, for a total of 28 instead of 17.

Uniting the nodes instead of their roots

✗ parent[u] = v;

✓ dsu.unite(u, v); // works on find(u) and find(v)

parent[u] = v moves node u itself, even when u is not a root, so u's old group loses its link. On the triangle 0–1 (1), 0–2 (2), 1–2 (3): keeping 0–1 sets parent[0] = 1. Then 0–2 sets parent[0] = 2 and cuts node 1 off from node 0. Now 1–2 looks like it joins two groups, so it is kept: total 6 instead of 3, and the kept edges contain a cycle. unite always works on the roots, so this cannot happen.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture