Minimum Spanning Tree (Kruskal)

🎯

Minimum Spanning Tree (Kruskal)

mediumGRAPHAmazonGoogleMicrosoft

Imagine you are designing a network of roads connecting cities with the least total construction cost, ensuring all cities are reachable.

💡 This problem is about connecting all points (nodes) in a graph with the minimum total edge weight without forming cycles. Beginners often struggle because it requires understanding how to efficiently detect cycles and pick edges in order of weight, which is not straightforward without a proper data structure like Union-Find.

📋

Problem Statement

Given an undirected weighted graph with n nodes and a list of edges where each edge connects two nodes and has a weight, find the minimum spanning tree (MST) of the graph. The MST is a subset of edges that connects all nodes with the minimum possible total edge weight and contains no cycles. Return the total weight of the MST.

1 ≤ n ≤ 10^51 ≤ number of edges ≤ 2 * 10^5Edge weights are positive integersThe graph is connected

💡

Example

Input"n = 4, edges = [[0,1,1],[1,2,2],[0,2,3],[2,3,4]]"

Output7

Pick edges (0,1), (1,2), and (2,3) with weights 1, 2, and 4 respectively. Total = 7, which is minimal.

• Graph with only one node → MST weight is 0
• Graph with all edges having the same weight → MST includes any n-1 edges without cycles
• Graph with multiple edges between same nodes → choose the smallest weight edge
• Graph with edges forming multiple cycles → MST excludes edges that form cycles

⚠️

Common Mistakes

Not sorting edges before processing

MST may not be minimal, incorrect total weight

✅ Always sort edges by weight ascending before union operations

Incorrect Union-Find implementation without path compression or union heuristics

Slower performance, possible stack overflow on deep recursion

✅ Implement path compression and union by rank or size

Not checking if all nodes are connected after union operations

MST may be incomplete if graph is disconnected, leading to wrong answers

✅ Verify MST has exactly n-1 edges or all nodes share the same root

Using 1-based indexing inconsistently with 0-based node labels

Array index errors or wrong unions leading to incorrect MST

✅ Be consistent with node indexing throughout code

Forgetting to stop early when MST has n-1 edges

Unnecessary processing, slower runtime

✅ Break loop once MST is complete

🧠

Brute Force (Check All Edge Subsets)

💡 This approach exists to understand the problem from first principles by trying all possible subsets of edges to find the MST. It is impractical for large inputs but helps grasp the MST definition and why optimization is needed.

Intuition

Try every combination of edges that connects all nodes without cycles and pick the one with the minimum total weight.

Algorithm

1. Generate all subsets of edges with size n-1 (since MST has n-1 edges).
2. For each subset, check if it connects all nodes and contains no cycles.
3. Calculate the total weight of the subset if valid.
4. Return the minimum total weight among all valid subsets.

💡 The challenge is enumerating subsets and checking connectivity and cycles, which is computationally expensive and hard to implement efficiently.

</>

Code

from itertools import combinations

def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(parent, rank, x, y):
    rx, ry = find(parent, x), find(parent, y)
    if rx == ry:
        return False
    if rank[rx] < rank[ry]:
        parent[rx] = ry
    elif rank[ry] < rank[rx]:
        parent[ry] = rx
    else:
        parent[ry] = rx
        rank[rx] += 1
    return True

def brute_force_mst(n, edges):
    if n == 1:
        return 0  # MST weight is 0 for single node
    min_weight = float('inf')
    for subset in combinations(edges, n - 1):
        parent = list(range(n))
        rank = [0] * n
        total = 0
        valid = True
        for u, v, w in subset:
            if not union(parent, rank, u, v):
                valid = False
                break
            total += w
        if valid:
            # Check if all nodes connected
            root = find(parent, 0)
            if all(find(parent, i) == root for i in range(n)):
                min_weight = min(min_weight, total)
    return min_weight if min_weight != float('inf') else -1

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [(0,1,1),(1,2,2),(0,2,3),(2,3,4)]
    print(brute_force_mst(n, edges))

Line Notes

from itertools import combinationsImport combinations to generate all edge subsets

def find(parent, x):Define find to locate root of a node for cycle detection

def union(parent, rank, x, y):Define union to merge sets and detect cycles

if n == 1:Handle single node graph where MST weight is 0

for subset in combinations(edges, n - 1):Try every subset of edges of size n-1

if not union(parent, rank, u, v):If union fails, a cycle is detected, discard subset

if all(find(parent, i) == root for i in range(n))Check if all nodes are connected

return min_weight if min_weight != float('inf') else -1Return MST weight or -1 if none found

import java.util.*;

public class BruteForceMST {
    static int find(int[] parent, int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    static boolean union(int[] parent, int[] rank, int x, int y) {
        int rx = find(parent, x);
        int ry = find(parent, y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
        return true;
    }

    static boolean nextCombination(int[] comb, int n, int k) {
        int i = k - 1;
        while (i >= 0 && comb[i] == n - k + i) i--;
        if (i < 0) return false;
        comb[i]++;
        for (int j = i + 1; j < k; j++) comb[j] = comb[j - 1] + 1;
        return true;
    }

    static int bruteForceMST(int n, List<int[]> edges) {
        if (n == 1) return 0; // MST weight is 0 for single node
        int minWeight = Integer.MAX_VALUE;
        int m = edges.size();
        int[] indices = new int[n - 1];
        for (int i = 0; i < n - 1; i++) indices[i] = i;

        while (true) {
            int[] parent = new int[n];
            int[] rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
            int total = 0;
            boolean valid = true;
            for (int idx : indices) {
                int[] e = edges.get(idx);
                if (!union(parent, rank, e[0], e[1])) {
                    valid = false;
                    break;
                }
                total += e[2];
            }
            if (valid) {
                int root = find(parent, 0);
                boolean connected = true;
                for (int i = 0; i < n; i++) {
                    if (find(parent, i) != root) {
                        connected = false;
                        break;
                    }
                }
                if (connected) minWeight = Math.min(minWeight, total);
            }
            if (!nextCombination(indices, m, n - 1)) break;
        }
        return minWeight == Integer.MAX_VALUE ? -1 : minWeight;
    }

    public static void main(String[] args) {
        int n = 4;
        List<int[]> edges = Arrays.asList(
            new int[]{0,1,1},
            new int[]{1,2,2},
            new int[]{0,2,3},
            new int[]{2,3,4}
        );
        System.out.println(bruteForceMST(n, edges));
    }
}

Line Notes

static int find(int[] parent, int x)Find root of x for cycle detection

static boolean union(int[] parent, int[] rank, int x, int y)Union sets and detect cycles

if (n == 1) return 0;Handle single node graph where MST weight is 0

for (int idx : indices)Iterate over current combination of edges

if (!union(parent, rank, e[0], e[1]))Cycle detected, discard this subset

if (!nextCombination(indices, m, n - 1)) break;Generate next combination of edges

int root = find(parent, 0);Check connectivity by verifying all nodes share root

return minWeight == Integer.MAX_VALUE ? -1 : minWeight;Return MST weight or -1 if none found

#include <bits/stdc++.h>
using namespace std;

int find_set(vector<int>& parent, int v) {
    while (parent[v] != v) v = parent[v];
    return v;
}

bool union_set(vector<int>& parent, vector<int>& rank, int a, int b) {
    a = find_set(parent, a);
    b = find_set(parent, b);
    if (a == b) return false;
    if (rank[a] < rank[b]) parent[a] = b;
    else if (rank[b] < rank[a]) parent[b] = a;
    else {
        parent[b] = a;
        rank[a]++;
    }
    return true;
}

bool next_combination(vector<int>& comb, int n, int k) {
    int i = k - 1;
    while (i >= 0 && comb[i] == n - k + i) i--;
    if (i < 0) return false;
    comb[i]++;
    for (int j = i + 1; j < k; j++) comb[j] = comb[j - 1] + 1;
    return true;
}

int brute_force_mst(int n, vector<array<int,3>>& edges) {
    if (n == 1) return 0; // MST weight is 0 for single node
    int m = (int)edges.size();
    vector<int> comb(n - 1);
    iota(comb.begin(), comb.end(), 0);
    int min_weight = INT_MAX;
    do {
        vector<int> parent(n), rank(n, 0);
        iota(parent.begin(), parent.end(), 0);
        int total = 0;
        bool valid = true;
        for (int idx : comb) {
            auto& e = edges[idx];
            if (!union_set(parent, rank, e[0], e[1])) {
                valid = false;
                break;
            }
            total += e[2];
        }
        if (valid) {
            int root = find_set(parent, 0);
            bool connected = true;
            for (int i = 0; i < n; i++) {
                if (find_set(parent, i) != root) {
                    connected = false;
                    break;
                }
            }
            if (connected) min_weight = min(min_weight, total);
        }
    } while (next_combination(comb, m, n - 1));
    return min_weight == INT_MAX ? -1 : min_weight;
}

int main() {
    int n = 4;
    vector<array<int,3>> edges = {{0,1,1},{1,2,2},{0,2,3},{2,3,4}};
    cout << brute_force_mst(n, edges) << "\n";
    return 0;
}

Line Notes

int find_set(vector<int>& parent, int v)Find root of node v for cycle detection

bool union_set(vector<int>& parent, vector<int>& rank, int a, int b)Union two sets and detect cycles

if (n == 1) return 0;Handle single node graph where MST weight is 0

do { ... } while (next_combination(comb, m, n - 1));Generate all combinations of edges

if (!union_set(parent, rank, e[0], e[1]))Cycle detected, discard this subset

int root = find_set(parent, 0);Check if all nodes connected by comparing roots

return min_weight == INT_MAX ? -1 : min_weight;Return MST weight or -1 if none found

function find(parent, x) {
    while (parent[x] !== x) {
        x = parent[x];
    }
    return x;
}

function union(parent, rank, x, y) {
    let rx = find(parent, x);
    let ry = find(parent, y);
    if (rx === ry) return false;
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[ry] < rank[rx]) parent[ry] = rx;
    else {
        parent[ry] = rx;
        rank[rx]++;
    }
    return true;
}

function nextCombination(comb, n, k) {
    let i = k - 1;
    while (i >= 0 && comb[i] === n - k + i) i--;
    if (i < 0) return false;
    comb[i]++;
    for (let j = i + 1; j < k; j++) {
        comb[j] = comb[j - 1] + 1;
    }
    return true;
}

function bruteForceMST(n, edges) {
    if (n === 1) return 0; // MST weight is 0 for single node
    let m = edges.length;
    let comb = Array.from({length: n - 1}, (_, i) => i);
    let minWeight = Infinity;
    do {
        let parent = Array.from({length: n}, (_, i) => i);
        let rank = Array(n).fill(0);
        let total = 0;
        let valid = true;
        for (let idx of comb) {
            let [u, v, w] = edges[idx];
            if (!union(parent, rank, u, v)) {
                valid = false;
                break;
            }
            total += w;
        }
        if (valid) {
            let root = find(parent, 0);
            let connected = true;
            for (let i = 0; i < n; i++) {
                if (find(parent, i) !== root) {
                    connected = false;
                    break;
                }
            }
            if (connected) minWeight = Math.min(minWeight, total);
        }
    } while (nextCombination(comb, m, n - 1));
    return minWeight === Infinity ? -1 : minWeight;
}

// Example usage
const n = 4;
const edges = [[0,1,1],[1,2,2],[0,2,3],[2,3,4]];
console.log(bruteForceMST(n, edges));

Line Notes

function find(parent, x)Find root of x for cycle detection

function union(parent, rank, x, y)Union sets and detect cycles

if (n === 1) return 0;Handle single node graph where MST weight is 0

do { ... } while (nextCombination(comb, m, n - 1));Generate all edge subsets of size n-1

if (!union(parent, rank, u, v))Cycle detected, discard this subset

let root = find(parent, 0);Check connectivity by verifying all nodes share root

return minWeight === Infinity ? -1 : minWeight;Return MST weight or -1 if none found

⏱

Complexity

TimeO(C(m, n-1) * n * α(n)) where C(m, n-1) is combinations of edges, α is inverse Ackermann

SpaceO(n) for Union-Find arrays

We try all subsets of edges of size n-1, which is combinatorial and grows exponentially. Each subset requires union-find operations to check cycles and connectivity.

💡 For n=4 and m=4 edges, this means checking 4 choose 3 = 4 subsets, which is manageable. For n=20, this explodes to billions of subsets, making it impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and why efficient algorithms like Kruskal's exist.

🧠

Kruskal's Algorithm with Union-Find

💡 This approach efficiently finds the MST by sorting edges by weight and using Union-Find to avoid cycles. It is the classic and optimal method for MST problems on sparse graphs.

Intuition

Sort edges by weight and add them one by one to the MST if they don't form a cycle, detected using Union-Find.

Algorithm

1. Sort all edges in non-decreasing order of their weight.
2. Initialize Union-Find data structure for all nodes.
3. Iterate over sorted edges, for each edge check if its endpoints belong to different sets.
4. If yes, union their sets and add the edge's weight to MST total.
5. Stop when MST contains n-1 edges.

💡 The key difficulty is understanding how Union-Find helps efficiently detect cycles and maintain connected components.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # Path compression
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

def kruskal_mst(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst_weight = 0
    edges_used = 0
    for u, v, w in edges:
        if uf.union(u, v):
            mst_weight += w
            edges_used += 1
            if edges_used == n - 1:
                break
    return mst_weight

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [(0,1,1),(1,2,2),(0,2,3),(2,3,4)]
    print(kruskal_mst(n, edges))

Line Notes

self.parent = list(range(n))Initialize each node as its own parent

self.rank = [0] * nInitialize rank array for union by rank optimization

while self.parent[x] != xTraverse up to find root parent with path compression

edges.sort(key=lambda x: x[2])Sort edges by weight ascending

if uf.union(u, v)Add edge if it connects two different components

if edges_used == n - 1Stop early when MST is complete

import java.util.*;

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // Path compression
            x = parent[x];
        }
        return x;
    }
    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
        return true;
    }
}

public class KruskalMST {
    public static int kruskalMST(int n, List<int[]> edges) {
        edges.sort(Comparator.comparingInt(a -> a[2]));
        UnionFind uf = new UnionFind(n);
        int mstWeight = 0, edgesUsed = 0;
        for (int[] e : edges) {
            if (uf.union(e[0], e[1])) {
                mstWeight += e[2];
                edgesUsed++;
                if (edgesUsed == n - 1) break;
            }
        }
        return mstWeight;
    }

    public static void main(String[] args) {
        int n = 4;
        List<int[]> edges = Arrays.asList(
            new int[]{0,1,1},
            new int[]{1,2,2},
            new int[]{0,2,3},
            new int[]{2,3,4}
        );
        System.out.println(kruskalMST(n, edges));
    }
}

Line Notes

parent = new int[n];Initialize parent array for Union-Find

rank = new int[n];Initialize rank array for union by rank

while (parent[x] != x)Find root with path compression

edges.sort(Comparator.comparingInt(a -> a[2]));Sort edges by weight ascending

if (uf.union(e[0], e[1]))Add edge if it connects different components

if (edgesUsed == n - 1) break;Stop early when MST complete

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // Path compression
            x = parent[x];
        }
        return x;
    }
    bool union_set(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
        return true;
    }
};

int kruskal_mst(int n, vector<array<int,3>>& edges) {
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
    UnionFind uf(n);
    int mst_weight = 0, edges_used = 0;
    for (auto& e : edges) {
        if (uf.union_set(e[0], e[1])) {
            mst_weight += e[2];
            edges_used++;
            if (edges_used == n - 1) break;
        }
    }
    return mst_weight;
}

int main() {
    int n = 4;
    vector<array<int,3>> edges = {{0,1,1},{1,2,2},{0,2,3},{2,3,4}};
    cout << kruskal_mst(n, edges) << "\n";
    return 0;
}

Line Notes

iota(parent.begin(), parent.end(), 0);Initialize each node as its own parent

while (parent[x] != x)Find root with path compression

sort(edges.begin(), edges.end(), ...Sort edges by ascending weight

if (uf.union_set(e[0], e[1]))Add edge if it connects different components

if (edges_used == n - 1) break;Stop early when MST complete

return mst_weight;Return total MST weight

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]]; // Path compression
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        let rx = this.find(x);
        let ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[ry] < this.rank[rx]) this.parent[ry] = rx;
        else {
            this.parent[ry] = rx;
            this.rank[rx]++;
        }
        return true;
    }
}

function kruskalMST(n, edges) {
    edges.sort((a,b) => a[2] - b[2]);
    const uf = new UnionFind(n);
    let mstWeight = 0, edgesUsed = 0;
    for (const [u,v,w] of edges) {
        if (uf.union(u, v)) {
            mstWeight += w;
            edgesUsed++;
            if (edgesUsed === n - 1) break;
        }
    }
    return mstWeight;
}

// Example usage
const n = 4;
const edges = [[0,1,1],[1,2,2],[0,2,3],[2,3,4]];
console.log(kruskalMST(n, edges));

Line Notes

this.parent = Array.from({length: n}, (_, i) => i);Initialize each node as its own parent

while (this.parent[x] !== x)Find root with path compression

edges.sort((a,b) => a[2] - b[2]);Sort edges by ascending weight

if (uf.union(u, v))Add edge if it connects different components

if (edgesUsed === n - 1) break;Stop early when MST complete

return mstWeight;Return total MST weight

⏱

Complexity

TimeO(m log m + m α(n)) where m is number of edges, α is inverse Ackermann

SpaceO(n) for Union-Find arrays

Sorting edges dominates with O(m log m). Union-Find operations are almost O(1) amortized. Overall efficient for large graphs.

💡 For m=10^5 edges, sorting takes about 10^5 * log(10^5) ≈ 5*10^5 operations, which is feasible in interviews.

Interview Verdict: Accepted

This is the standard and optimal approach for MST problems, expected in interviews.

🧠

Kruskal's Algorithm with Union-Find (Path Compression + Union by Size)

💡 This approach optimizes Union-Find by using union by size instead of rank, which is an alternative heuristic to keep trees shallow and improve performance.

Intuition

Same as Kruskal's, but union merges smaller set into larger to keep tree height minimal, improving find operation speed.

Algorithm

1. Sort edges by weight ascending.
2. Initialize Union-Find with size array for each node.
3. For each edge, union sets by attaching smaller set to larger.
4. Add edge weight if union succeeds.
5. Stop when MST has n-1 edges.

💡 Union by size is easier to implement and achieves similar performance to union by rank.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # Path compression
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            self.parent[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.parent[ry] = rx
            self.size[rx] += self.size[ry]
        return True

def kruskal_mst_union_by_size(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst_weight = 0
    edges_used = 0
    for u, v, w in edges:
        if uf.union(u, v):
            mst_weight += w
            edges_used += 1
            if edges_used == n - 1:
                break
    return mst_weight

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [(0,1,1),(1,2,2),(0,2,3),(2,3,4)]
    print(kruskal_mst_union_by_size(n, edges))

Line Notes

self.size = [1] * nInitialize size array to track component sizes

if self.size[rx] < self.size[ry]Attach smaller tree under larger to keep shallow

self.size[ry] += self.size[rx]Update size after union

edges.sort(key=lambda x: x[2])Sort edges by weight ascending

if uf.union(u, v)Add edge if it connects different components

if edges_used == n - 1Stop early when MST complete

import java.util.*;

class UnionFind {
    int[] parent, size;
    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // Path compression
            x = parent[x];
        }
        return x;
    }
    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size[rx] < size[ry]) {
            parent[rx] = ry;
            size[ry] += size[rx];
        } else {
            parent[ry] = rx;
            size[rx] += size[ry];
        }
        return true;
    }
}

public class KruskalMSTUnionBySize {
    public static int kruskalMST(int n, List<int[]> edges) {
        edges.sort(Comparator.comparingInt(a -> a[2]));
        UnionFind uf = new UnionFind(n);
        int mstWeight = 0, edgesUsed = 0;
        for (int[] e : edges) {
            if (uf.union(e[0], e[1])) {
                mstWeight += e[2];
                edgesUsed++;
                if (edgesUsed == n - 1) break;
            }
        }
        return mstWeight;
    }

    public static void main(String[] args) {
        int n = 4;
        List<int[]> edges = Arrays.asList(
            new int[]{0,1,1},
            new int[]{1,2,2},
            new int[]{0,2,3},
            new int[]{2,3,4}
        );
        System.out.println(kruskalMST(n, edges));
    }
}

Line Notes

size = new int[n];Initialize size array for union by size

if (size[rx] < size[ry])Attach smaller tree under larger

size[ry] += size[rx];Update size after union

edges.sort(Comparator.comparingInt(a -> a[2]));Sort edges by weight ascending

if (uf.union(e[0], e[1]))Add edge if it connects different components

if (edgesUsed == n - 1) break;Stop early when MST complete

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent, size;
    UnionFind(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // Path compression
            x = parent[x];
        }
        return x;
    }
    bool union_set(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size[rx] < size[ry]) {
            parent[rx] = ry;
            size[ry] += size[rx];
        } else {
            parent[ry] = rx;
            size[rx] += size[ry];
        }
        return true;
    }
};

int kruskal_mst(int n, vector<array<int,3>>& edges) {
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
    UnionFind uf(n);
    int mst_weight = 0, edges_used = 0;
    for (auto& e : edges) {
        if (uf.union_set(e[0], e[1])) {
            mst_weight += e[2];
            edges_used++;
            if (edges_used == n - 1) break;
        }
    }
    return mst_weight;
}

int main() {
    int n = 4;
    vector<array<int,3>> edges = {{0,1,1},{1,2,2},{0,2,3},{2,3,4}};
    cout << kruskal_mst(n, edges) << "\n";
    return 0;
}

Line Notes

size(n, 1)Initialize size array with 1 for each node

if (size[rx] < size[ry])Attach smaller tree under larger

size[ry] += size[rx];Update size after union

sort(edges.begin(), edges.end(), ...Sort edges by ascending weight

if (uf.union_set(e[0], e[1]))Add edge if it connects different components

if (edges_used == n - 1) break;Stop early when MST complete

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.size = Array(n).fill(1);
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]]; // Path compression
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        let rx = this.find(x);
        let ry = this.find(y);
        if (rx === ry) return false;
        if (this.size[rx] < this.size[ry]) {
            this.parent[rx] = ry;
            this.size[ry] += this.size[rx];
        } else {
            this.parent[ry] = rx;
            this.size[rx] += this.size[ry];
        }
        return true;
    }
}

function kruskalMSTUnionBySize(n, edges) {
    edges.sort((a,b) => a[2] - b[2]);
    const uf = new UnionFind(n);
    let mstWeight = 0, edgesUsed = 0;
    for (const [u,v,w] of edges) {
        if (uf.union(u, v)) {
            mstWeight += w;
            edgesUsed++;
            if (edgesUsed === n - 1) break;
        }
    }
    return mstWeight;
}

// Example usage
const n = 4;
const edges = [[0,1,1],[1,2,2],[0,2,3],[2,3,4]];
console.log(kruskalMSTUnionBySize(n, edges));

Line Notes

this.size = Array(n).fill(1);Initialize size array for union by size

if (this.size[rx] < this.size[ry])Attach smaller tree under larger

this.size[ry] += this.size[rx];Update size after union

edges.sort((a,b) => a[2] - b[2]);Sort edges by ascending weight

if (uf.union(u, v))Add edge if it connects different components

if (edgesUsed === n - 1) break;Stop early when MST complete

⏱

Complexity

TimeO(m log m + m α(n)) same as union by rank

SpaceO(n) for Union-Find arrays

Union by size is an alternative heuristic with similar time complexity and performance to union by rank.

💡 This variant is easier to implement and equally efficient for interview purposes.

Interview Verdict: Accepted

This is a valid and efficient alternative to union by rank, demonstrating understanding of Union-Find optimizations.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code Kruskal's algorithm with Union-Find (Approach 2 or 3). Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(C(m, n-1) * n * α(n)) exponential	O(n)	No	Yes	Mention only - never code
2. Kruskal's with Union-Find (Rank)	O(m log m)	O(n)	No	Yes	Code this in 95% of MST interviews
3. Kruskal's with Union-Find (Size)	O(m log m)	O(n)	No	Yes	Valid alternative to union by rank

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs and optimizations clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of MST definition.Introduce Kruskal's algorithm and Union-Find for cycle detection.Discuss Union-Find optimizations like path compression and union by rank/size.Write clean, tested code and analyze complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test & Optimize: 7min. Total ~25min

What the Interviewer Tests

Interviewer tests your grasp of MST concepts, ability to implement Union-Find correctly, and optimize for performance and clarity.

Common Follow-ups

• How would you implement Prim's algorithm and compare it to Kruskal's?
• How does Union-Find help detect cycles efficiently?
• What if the graph is disconnected?
• Can you modify the algorithm to return the actual MST edges?

💡 These follow-ups test deeper understanding of MST algorithms, data structures, and edge cases.

🔍

Pattern Recognition

When to Use

1) Need to connect all nodes with minimal total edge weight, 2) Graph is undirected and weighted, 3) Problem mentions MST or minimal connection cost, 4) Cycle detection is required.

Signature Phrases

minimum spanning treeconnect all nodes with minimum costno cyclesunion-finddisjoint set

NOT This Pattern When

Shortest path problems (Dijkstra), Maximum spanning tree, or MST in directed graphs

Similar Problems

Prim's Minimum Spanning Tree - alternative MST algorithm using priority queueDisjoint Set Union (DSU) Basics - foundational data structure for cycle detectionCycle Detection in Undirected Graph - core concept behind MST correctness

Practice

1. Given the following code snippet implementing union-find for accounts merge, what is the final output of accountsMerge when called with accounts = [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]?

easy

A. [["John", "[e-mail]", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]

B. [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]

C. [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]"], ["Mary", "[e-mail]"]]

D. [["Mary", "[e-mail]"], ["John", "[e-mail]", "[e-mail]", "[e-mail]"]]

Solution

1. Step 1: Trace union operations

   All emails in John's accounts are unioned: "[e-mail]", "[e-mail]", and "[e-mail]" become one set.

2. Step 2: Group emails by root and sort

   Mary's email is separate. John's merged emails are sorted alphabetically.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   John's emails merged correctly; Mary's account unchanged [OK]

Hint: Union-find merges all connected emails into one set [OK]

Common Mistakes:

• Forgetting to union all emails in an account
• Not sorting emails before output

2. You are given a network of cities represented as an n x n matrix where isConnected[i][j] = 1 means city i is directly connected to city j. Your task is to find how many groups of cities are connected directly or indirectly. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that picks the city with the most connections first

B. Sorting cities by their connection counts and merging groups

C. Graph traversal using DFS or BFS to find connected components

D. Dynamic programming to count paths between cities

Solution

1. Step 1: Understand the problem as finding connected components in a graph

   The problem describes a graph where nodes are cities and edges represent direct connections. The goal is to find how many connected groups exist.

2. Step 2: Identify the algorithm that finds connected components efficiently

   DFS or BFS traversals can explore all nodes reachable from a starting node, marking them visited. Counting how many times you start a new traversal gives the number of connected components.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Connected components are found by graph traversal [OK]

Hint: Connected components -> DFS/BFS traversal [OK]

Common Mistakes:

• Thinking greedy or sorting can find connected components
• Confusing path counting with component counting

3. Consider the following Python code implementing Union-Find with path compression and union by rank to find a redundant connection. Given the input edges [[1, 2], [1, 3], [2, 3]], what is the output of the function?

easy

A. [1, 2]

B. [1, 3]

C. [2, 3]

D. None (no redundant edge)

Solution

1. Step 1: Trace union operations for edges [1,2], [1,3], [2,3]

   Union(1,2) succeeds, Union(1,3) succeeds, Union(2,3) fails because 2 and 3 are already connected.

2. Step 2: Identify returned edge

   The first edge that causes union to fail is [2,3], so it is returned as redundant.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-Find detects cycle at edge [2,3] [OK]

Hint: Union fails when both nodes share the same root [OK]

Common Mistakes:

• Returning first edge instead of the one causing cycle
• Confusing union success/failure
• Off-by-one indexing errors

4. What is the time complexity of the optimal union-find based solution for the Accounts Merge problem, where N is the number of accounts and M is the maximum number of emails per account?

medium

A. O(N^2 * M) because each account is compared with every other

B. O(N * M^2) due to nested loops over emails

C. O(N * M * α(N * M)) where α is the inverse Ackermann function

D. O(N * M log (N * M)) due to sorting emails after union

Solution

1. Step 1: Identify union-find operations cost

   Union-find operations (union/find) run in nearly O(1) amortized time, specifically O(α(N*M)) per operation.

2. Step 2: Count total operations

   We perform union operations for each email in each account, totaling O(N*M) unions and finds.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-find with path compression yields almost linear time [OK]

Hint: Union-find nearly linear with inverse Ackermann factor [OK]

Common Mistakes:

• Confusing sorting cost with union-find cost
• Assuming quadratic due to nested loops

5. Suppose the problem is extended so that variables can be reused multiple times in equations, and inequalities can be chained (e.g., a==b, b!=c, c==a). Which modification to the union-find approach correctly handles early contradiction detection in this scenario?

hard

A. Process all equalities and inequalities in a single pass, unioning and checking contradictions immediately

B. First union all equalities, then check all inequalities for contradictions, returning false if any found

C. Use union-find with early contradiction detection by checking inequalities during union operations and aborting immediately on conflict

D. Replace union-find with a graph coloring approach to handle chained inequalities

Solution

1. Step 1: Understand reuse and chaining impact

   Variables appearing multiple times and chained inequalities require detecting contradictions as soon as they arise to avoid unnecessary work.

2. Step 2: Early contradiction detection

   Checking inequalities during union operations allows immediate detection of conflicts, improving efficiency and correctness.

3. Step 3: Compare alternatives

   Single pass union and check can miss contradictions; two-pass delays detection; graph coloring is more complex and less efficient here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Early contradiction detection aborts on conflict [OK]

Hint: Check contradictions during union to detect conflicts early [OK]

Common Mistakes:

• Checking inequalities only after all unions
• Trying single pass union and check without order