How to Solve: Minimum Spanning Tree (Prim’s / Kruskal’s) – Complete Guide for FAANG Interviews

How to Solve: Minimum Spanning Tree (Prim’s / Kruskal’s) – Complete Guide for FAANG Interviews

? Introduction

"Minimum Spanning Tree problems appear in 1 out of every 5 graph-related interviews—mastering Prim’s and Kruskal’s doesn’t just solve the problem, it proves you can optimize real-world networks like Amazon’s delivery routes or Google’s data center connections."

? WHAT YOU NEED TO KNOW FIRST

Before tackling MST problems, ensure you understand: 1. Graph Representations (Adjacency List vs. Matrix) – Know when to use each. 2. Union-Find (Disjoint Set Union - DSU) – Critical for Kruskal’s algorithm. 3. Priority Queues (Min-Heap) – Essential for Prim’s algorithm.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps for every MST problem:

1. Understand the Problem

• Is the graph undirected? (MSTs only work on undirected graphs.)
• Are edges weighted? (If unweighted, BFS/DFS suffices.)
• Is the graph connected? (If not, return -1 or handle disconnected components.)

2. Choose the Right Algorithm

• Prim’s: Best for dense graphs (E ≈ V²) or when you need to start from a specific node.
• Kruskal’s: Best for sparse graphs (E ≈ V) or when edges are pre-sorted.

3. Implement the Algorithm

Prim’s (Lazy Version)

1. Initialize:
2. min_heap = [] (store (weight, node))
3. visited = set() (track nodes in MST)
4. mst_weight = 0
5. Start from any node (e.g., node 0):
6. Push all edges from node 0 into the heap.
7. Mark node 0 as visited.
8. While heap is not empty:
9. Pop the smallest edge (weight, node).
10. If node is already visited, skip.
11. Else, add weight to mst_weight, mark node as visited, and push all its edges into the heap.
12. Return mst_weight (or -1 if graph is disconnected).

Kruskal’s

1. Sort all edges by weight (ascending).
2. Initialize Union-Find (DSU) for cycle detection.
3. Iterate through sorted edges:
4. For each edge (u, v, weight), check if u and v are in the same set (find(u) == find(v)).
5. If not, union them and add weight to mst_weight.
6. Return mst_weight (or -1 if graph is disconnected).

4. Handle Edge Cases

• Disconnected graph: Return -1 or handle components separately.
• Negative weights: MST algorithms work with negative weights (unlike Dijkstra’s).
• Multiple edges between nodes: Keep the smallest one (or handle duplicates in sorting).

5. Optimize for Time/Space

• Prim’s: O(E log E) with a binary heap, O(E + V log V) with a Fibonacci heap.
• Kruskal’s: O(E log E) (sorting) + O(E α(V)) (Union-Find), where α is the inverse Ackermann function (effectively O(1)).

? WORKED EXAMPLES

Example 1 – Basic: Find MST Weight (Prim’s)

Problem: Given an undirected, connected graph with weighted edges, find the total weight of the MST.

Graph:

      2
  0------1
  | \    |
3 |  \1  | 4
  |   \  |
  2------3

      5

Solution (Prim’s - Lazy):

import heapq

def prim_mst(graph, start=0):

    n = len(graph)

    min_heap = []

    visited = set()

    mst_weight = 0


    # Start with node 0

    heapq.heappush(min_heap, (0, start))


    while min_heap:

        weight, node = heapq.heappop(min_heap)

        if node in visited:

            continue

        visited.add(node)

        mst_weight += weight

        for neighbor, edge_weight in graph[node]:

            if neighbor not in visited:

                heapq.heappush(min_heap, (edge_weight, neighbor))


    return mst_weight if len(visited) == n else -1

# Adjacency list representation
graph = [

    [(1, 2), (2, 3), (3, 1)],  # Node 0

    [(0, 2), (3, 4)],          # Node 1

    [(0, 3), (3, 5)],          # Node 2

    [(0, 1), (1, 4), (2, 5)]   # Node 3
]

print(prim_mst(graph))  # Output: 6 (0-3:1, 0-1:2, 0-2:3)

Why this works: - Prim’s greedily picks the smallest edge connecting the MST to a new node, ensuring no cycles. - The min-heap ensures we always process the smallest available edge.

Time Complexity: O(E log E) (each edge is pushed/popped from the heap once). Space Complexity: O(E) (heap storage).

Example 2 – Medium: Kruskal’s with Union-Find

Problem: Same as Example 1, but implement Kruskal’s.

Solution:

class UnionFind:

    def __init__(self, size):

        self.parent = list(range(size))

        self.rank = [0]  size


    def find(self, x):

        if self.parent[x] != x:

            self.parent[x] = self.find(self.parent[x])  # Path compression

        return self.parent[x]


    def union(self, x, y):

        x_root = self.find(x)

        y_root = self.find(y)

        if x_root == y_root:

            return False  # Already in the same set

        # Union by rank

        if self.rank[x_root] < self.rank[y_root]:

            self.parent[x_root] = y_root

        else:

            self.parent[y_root] = x_root

            if self.rank[x_root] == self.rank[y_root]:

                self.rank[x_root] += 1

        return True

def kruskal_mst(edges, n):

    edges.sort()  # Sort by weight

    uf = UnionFind(n)

    mst_weight = 0

    edges_used = 0


    for weight, u, v in edges:

        if uf.union(u, v):

            mst_weight += weight

            edges_used += 1

            if edges_used == n - 1:

                break


    return mst_weight if edges_used == n - 1 else -1

# Edge list: (weight, u, v)
edges = [

    (1, 0, 3),

    (2, 0, 1),

    (3, 0, 2),

    (4, 1, 3),

    (5, 2, 3)
]
n = 4  # Number of nodes

print(kruskal_mst(edges, n))  # Output: 6

Why this works: - Kruskal’s sorts edges and adds them in order, skipping those that form cycles (using Union-Find). - Union-Find ensures O(α(V)) per operation, making the algorithm efficient.

Time Complexity: O(E log E) (sorting) + O(E α(V)) (Union-Find). Space Complexity: O(V) (Union-Find storage).

Example 3 – Hard: Minimum Cost to Connect All Points (LeetCode 1584)

Problem: Given n points in a 2D plane, connect them into a single component with the minimum total edge cost (Manhattan distance).

Solution (Prim’s):

import heapq

def minCostConnectPoints(points):

    n = len(points)

    if n == 1:

        return 0


    # Build adjacency list (all possible edges)

    graph = [[] for _ in range(n)]

    for i in range(n):

        x1, y1 = points[i]

        for j in range(i + 1, n):

            x2, y2 = points[j]

            dist = abs(x1 - x2) + abs(y1 - y2)

            graph[i].append((j, dist))

            graph[j].append((i, dist))


    # Prim's algorithm

    min_heap = []

    visited = set()

    mst_weight = 0


    # Start with node 0

    heapq.heappush(min_heap, (0, 0))


    while min_heap:

        weight, node = heapq.heappop(min_heap)

        if node in visited:

            continue

        visited.add(node)

        mst_weight += weight

        for neighbor, edge_weight in graph[node]:

            if neighbor not in visited:

                heapq.heappush(min_heap, (edge_weight, neighbor))


    return mst_weight

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
print(minCostConnectPoints(points))  # Output: 20

Why this works: - The problem reduces to finding an MST where edges are Manhattan distances between points. - Prim’s is efficient here because the graph is dense (each point connects to every other point).

Time Complexity: O(V² log V) (V² edges, each processed once in the heap). Space Complexity: O(V²) (adjacency list storage).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Minimum Spanning Trees are about connecting all nodes with the least total edge weight. Here’s the playbook:

1. Choose your algorithm: Prim’s for dense graphs, Kruskal’s for sparse.
2. Prim’s: Start at a node, use a min-heap to greedily pick the smallest edge connecting to the MST. Skip visited nodes.
3. Kruskal’s: Sort edges, use Union-Find to add edges without cycles.
4. Edge cases: Disconnected graphs? Return -1. Negative weights? No problem.
5. Optimize: Prim’s with a Fibonacci heap for O(E + V log V), Kruskal’s with Union-Find for O(E log E).

Walk in, write the code, and own the problem. You’ve got this." ?