Core Insight Improve a node’s known cost only when a newly discovered path is genuinely better.
Common Pitfall Discard stale priority-queue entries instead of expanding them a second time.
Description
Find minimum cost to connect all points (Minimum Spanning Tree).
Constraints
- Time Complexity:
O(n² log n) - Space Complexity:
O(n²)
Tags
arrayunion-findgraphminimum-spanning-tree
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize distances and a frontier.
- Take the cheapest candidate.
- Relax each outgoing edge.
- Repeat until the target or all reachable nodes are settled.
def minCostConnectPoints(points):
N = len(points)
adj = {i: [] for i 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)
adj[i].append([dist, j])
adj[j].append([dist, i])
res = 0
visit = set()
minH = [[0, 0]]
while len(visit) < N:
cost, i = heapq.heappop(minH)
if i in visit:
continue
res += cost
visit.add(i)
for neiCost, nei in adj[i]:
if nei not in visit:
heapq.heappush(minH, [neiCost, nei])
return res