Min Cost to Connect All Points: Minimum Spanning Tree

You are given an array of points where points[i] = [xi, yi] represents a point on a 2D plane. The cost of connecting two points is the Manhattan distance between them: |xi - xj| + |yi - yj|. Return the minimum cost to make all points connected, where any two points have exactly one simple path between them.

This is LeetCode 1584: Min Cost to Connect All Points, and it is one of the cleanest problems for learning Minimum Spanning Trees (MST). The technique it teaches, Kruskal's algorithm with Union-Find, applies to any problem where you need to connect nodes at minimum total cost.

Why this problem matters

Minimum spanning trees are fundamental in graph theory. They show up in network design (connecting cities with the least cable), clustering algorithms, and approximation algorithms for harder problems like the traveling salesman. The MST pattern also introduces Union-Find, one of the most versatile data structures in competitive programming and interviews.

This problem is special because the graph is complete: every pair of points has an edge. That means you cannot just read edges from the input. You have to generate all n*(n-1)/2 edges yourself. Once you do that, the rest is classic Kruskal's.

The key insight

This is a minimum spanning tree problem on a complete graph. Every pair of points forms an edge with cost equal to the Manhattan distance. You need to select exactly n-1 edges that connect all points with the smallest total cost and no cycles.

Kruskal's algorithm handles this: sort all edges by cost, then greedily add the cheapest edge that does not create a cycle. To detect cycles efficiently, you use Union-Find (also called Disjoint Set Union). Two points are in the same component if they are already connected. If an edge connects two points in the same component, skip it. Otherwise, union them and add the edge to the MST.

The algorithm:

1. Generate all n*(n-1)/2 edges with their Manhattan distances.
2. Sort edges by cost.
3. Initialize Union-Find with n components (one per point).
4. Iterate through sorted edges. For each edge, if the two endpoints are in different components, union them and add the cost to the total.
5. Stop once you have selected n-1 edges.

The solution

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]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((cost, i, j))

    edges.sort()
    uf = UnionFind(n)
    total = 0
    count = 0

    for cost, u, v in edges:
        if uf.union(u, v):
            total += cost
            count += 1
            if count == n - 1:
                break

    return total

Let's walk through what each piece does.

The UnionFind class tracks which points belong to the same connected component. The find method uses path compression (path halving), which keeps the tree flat and makes repeated lookups nearly constant time. The union method merges two components using union by rank, attaching the shorter tree under the taller one. It returns False if the two elements are already in the same component, which is how we detect cycles.

The main function first generates every possible edge. For n points, there are n*(n-1)/2 edges. Each edge is a tuple (cost, i, j) where cost is the Manhattan distance. We sort all edges by cost so the cheapest ones come first.

Then we iterate through the sorted edges. For each edge, we try to union its two endpoints. If union returns True, the edge connects two different components, so we add it to the MST. We track the count of selected edges and stop as soon as we have n-1 (which is all you need to connect n nodes in a tree).

Visual walkthrough

Let's trace Kruskal's algorithm on four points: A(0,0), B(1,1), C(1,3), D(3,1). There are 6 edges total, three at cost 2 and three at cost 4.

Notice the pattern: we never look at the cost-4 edges because the MST completes with three cost-2 edges. The early termination check saves us from processing the remaining half of the edge list. Also notice that every time we pick an edge, we are merging two previously disconnected components. The moment we try to add an edge whose endpoints are already connected (same component), we skip it to avoid a cycle.

Complexity analysis

Time is O(n^2 log n). Generating all edges takes O(n^2) since there are n*(n-1)/2 pairs. Sorting those edges takes O(n^2 log n^2) = O(n^2 log n). The Union-Find operations across all edges are nearly O(n^2) with path compression and union by rank (inverse Ackermann factor is practically constant). Sorting dominates.

Space is O(n^2) because you store all n*(n-1)/2 edges. The Union-Find structure itself is only O(n), but the edge list dominates.

An alternative is Prim's algorithm, which avoids storing all edges at once and can run in O(n^2) time with an adjacency matrix approach. For this problem's constraints (n up to 1000), either approach works well.

The building blocks

1. Complete graph edge generation

The pattern of generating all pairwise edges from a set of nodes:

edges = []
for i in range(n):
    for j in range(i + 1, n):
        cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
        edges.append((cost, i, j))

The key detail is using j in range(i + 1, n) instead of range(n) to avoid duplicate edges and self-loops. Each pair (i, j) appears exactly once. This pattern shows up in any problem where you need to compute pairwise relationships: closest pair of points, graph construction from coordinates, and similarity computations.

2. Kruskal's algorithm with early termination

The pattern of building an MST by greedily selecting the cheapest edge that does not form a cycle:

edges.sort()
uf = UnionFind(n)
total = 0
count = 0

for cost, u, v in edges:
    if uf.union(u, v):
        total += cost
        count += 1
        if count == n - 1:
            break

This is Kruskal's algorithm in its purest form. Sort edges, iterate, union if possible, stop at n-1 edges. The Union-Find makes cycle detection O(alpha(n)) per operation. You will reuse this exact template in problems like "Connecting Cities With Minimum Cost" (LeetCode 1135), "Optimize Water Distribution in a Village" (LeetCode 1168), and any minimum spanning tree variant.

Edge cases

Before submitting, think through these scenarios:

• Single point: n = 1, no edges needed. The answer is 0. The loop does not execute.
• Two points: only one edge exists. The answer is the Manhattan distance between them. One union, done.
• All points at the same location: every edge has cost 0. The MST has n-1 edges, all with cost 0. Total is 0.
• Points in a line: for example, [[0,0],[1,0],[2,0],[3,0]]. The MST connects consecutive points. Each edge has cost 1, total is n-1.
• Large coordinates: Manhattan distances can be large (up to 2 * 10^6 per edge), but the sum still fits in a 32-bit integer for the given constraints.
• All equal Manhattan distances: every edge has the same cost. Any spanning tree is an MST. Kruskal's picks an arbitrary one based on sort order.

From understanding to recall

You have seen how Kruskal's algorithm with Union-Find builds the MST: generate edges, sort, greedily pick the cheapest that does not create a cycle, stop at n-1. The logic is elegant and the code is compact. But reproducing it cleanly under interview pressure is a different challenge.

The details that trip people up: remembering to generate edges with j > i to avoid duplicates, implementing path compression and union by rank correctly, returning False from union when both elements share the same root, and knowing to stop at n-1 edges. These are not conceptual difficulties. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice writing the Union-Find class and Kruskal's loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "connect all nodes at minimum cost" in a problem description, and the MST template flows out without hesitation.

Related posts

• Course Schedule - Graph traversal with dependency tracking using topological sort
• Number of Provinces - Union-Find for counting connected components
• Accounts Merge - Union-Find grouping pattern for merging overlapping sets

CodeBricks breaks Min Cost to Connect All Points into its edge generation and Kruskal's with Union-Find building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an MST problem shows up in your interview, you do not think about it. You just write it.