Min Cost to Connect All Points

Min Cost to Connect All Points medium

Description

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to make all points connected. All points will be connected if there is exactly one simple path between any two points.

Examples

> Case 1:
    points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
    Output: 20
 
> Case 2:
    points = [[3,12],[-2,5],[-4,1]]
    Output: 18

Constraints

1 <= points.length <= 1000
-10^6 <= xi, yi <= 10^6
All pairs of points are distinct.

State design / Intuition

This is a pure MST problem on a complete graph where edge weight = Manhattan distance between every pair. With n ≤ 1000, the complete graph has up to n(n-1)/2 ≈ 500,000 edges — Kruskal’s with sorting all edges works (O(n² log n)) but Prim’s dense O(n²) variant is cleaner and faster by a log factor.

Prim’s dense approach:

Maintain key[v] = the minimum distance from v to the current tree.
At each step, pick the unvisited vertex with the smallest key.
Update neighbors’ keys with the distance to the newly added vertex.

No need to explicitly store all edges — distances are computed on the fly.

Code — Prim’s O(n²)

Code — Kruskal’s O(n² log n)

For reference — works but slower:

def minCostConnectPoints_kruskal(points):
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((d, i, j))
    edges.sort()
 
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
 
    total = added = 0
    for d, u, v in edges:
        pu, pv = find(u), find(v)
        if pu != pv:
            parent[pu] = pv
            total += d
            added += 1
            if added == n - 1: break
    return total

Analysis

Approach	Time	Space
Prim’s dense	O(n²)	O(n)
Kruskal’s	O(n² log n)	O(n²) for edge list

For n ≤ 1000, both pass. Prim’s is preferred since it avoids allocating and sorting O(n²) edges.

Same skin

Euclidean MST — same structure with sqrt((dx)² + (dy)²) instead of Manhattan distance.
Minimum cost to connect islands — BFS/DFS to find island cells, then MST on island centroids.
Clustering k groups — run Prim’s MST, then remove the k−1 heaviest edges.

Overview Redundant Connection