TL;DR
Minimum spanning tree; Prim’s algorithm with an array (dense graph) — O(n²) time, O(n) space.
Approach 1 — Brute force (try every candidate tree)
A spanning tree has exactly n - 1 edges, so the naive idea is: enumerate every subset of n - 1 edges, keep the ones that connect all points, and take the cheapest.
from itertools import combinations
class Solution:
def minCostConnectPoints(self, points: list[list[int]]) -> int:
n = len(points)
if n == 1:
return 0
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))
best = float("inf")
for subset in combinations(edges, n - 1):
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
x = parent[x]
return x
cost = 0
joins = 0
for d, i, j in subset:
ri, rj = find(i), find(j)
if ri != rj:
parent[ri] = rj
joins += 1
cost += d
if joins == n - 1:
best = min(best, cost)
return best
Complexity: C(n²/2, n−1) subsets — super-exponential. Already hopeless at n = 6; the constraint n <= 1000 kills it outright.
Approach 2 — Kruskal’s algorithm + union-find
The insight: the MST greedy-choice property says the cheapest edge crossing any cut is safe to take. Kruskal’s algorithm (sort all edges ascending; take an edge iff its endpoints are in different components) exploits this directly. A union-find / DSU (a forest of pointers with near-O(1) find and union, thanks to path compression and union by rank) answers “same component?” fast.
class DSU:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
class Solution:
def minCostConnectPoints(self, points: list[list[int]]) -> int:
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()
dsu = DSU(n)
total = taken = 0
for d, i, j in edges:
if dsu.union(i, j):
total += d
taken += 1
if taken == n - 1:
break
return total
Walkthrough (points = [[0,0],[2,2],[3,10],[5,2],[7,0]], indices 0–4): sorted edge list starts (3, 1, 3), (4, 0, 1), (4, 3, 4), (7, 0, 3), (7, 0, 4), (7, 1, 4), (9, 1, 2), .... Take 3 (joins 1,3), take 4 (joins 0 into {1,3}), take 4 (joins 4), skip the three 7s (all inside {0,1,3,4}), take 9 (joins 2). Total 3 + 4 + 4 + 9 = 20. Four edges taken = n - 1, stop.
Complexity: O(n² log n) time (sorting ~n²/2 edges dominates), O(n²) space for the edge list.
Approach 3 — Prim’s algorithm, array version (best for dense graphs)
The insight: Prim’s algorithm grows the tree from one seed point: at each step, absorb the outside point whose connection to the tree is cheapest. In a complete graph, a heap buys nothing — there are Θ(n²) edges anyway — so keep a plain array min_edge[v] = cheapest cost from v to the current tree, scan it for the minimum, and update it after each absorption. No edge list, no sort, O(n) memory.
class Solution:
def minCostConnectPoints(self, points: list[list[int]]) -> int:
n = len(points)
in_tree = [False] * n
min_edge = [float("inf")] * n
min_edge[0] = 0
total = 0
for _ in range(n):
u = -1
for v in range(n):
if not in_tree[v] and (u == -1 or min_edge[v] < min_edge[u]):
u = v
in_tree[u] = True
total += min_edge[u]
ux, uy = points[u]
for v in range(n):
if not in_tree[v]:
d = abs(ux - points[v][0]) + abs(uy - points[v][1])
if d < min_edge[v]:
min_edge[v] = d
return total
Walkthrough (same example): absorb point 0, min_edge becomes [-, 4, 13, 7, 7]. Cheapest outside is point 1 (cost 4); after updating, min_edge = [-, -, 9, 3, 7] (point 3 is only 3 away from (2,2)). Absorb point 3 (cost 3) → point 4 drops to 4. Absorb point 4 (cost 4). Absorb point 2 (cost 9). Total 4 + 3 + 4 + 9 = 20.
Complexity: O(n²) time, O(n) space — optimal for a complete graph and the intended solution.
Common pitfalls
- Reaching for heap-based Prim or Kruskal by reflex: on a complete graph they cost O(n² log n); array Prim is O(n²) and uses O(n) memory instead of materializing 500k edges.
- Union-find without path compression or rank degrades toward O(n) per operation on adversarial inputs.
- Forgetting that with Kruskal you must skip (not fail on) edges inside one component, and that you can stop after
n - 1 accepted edges.
- Computing Euclidean instead of Manhattan distance.
Pattern takeaway
When a problem says “connect everything at minimum total cost” with no path-length requirements, it’s a minimum spanning tree, not a shortest-path problem — Dijkstra optimizes point-to-point distances, MST optimizes total wiring. Then match the algorithm to density: sparse edge list → Kruskal + DSU; dense or complete graph → array Prim at O(n²).