LeetCode 1584 · Medium · Advanced Graphs

Min Cost to Connect All Points

Connecting two points costs their Manhattan distance, |x1 − x2| + |y1 − y2|. Return the smallest total cost that links every point to every other, directly or through other points.

O(n² log n)time
O(n²)space
Primgrow one tree, cheapest edge out

points separated by ";" · 1–7 points · x and y −20 to 20 · no duplicate points

minH · [cost, point], cheapest first

public int minCostConnectPoints(int[][] points) { int N = points.length; List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i < N; i++) { adj.add(new ArrayList<>()); } for (int i = 0; i < N; i++) { int x1 = points[i][0]; int y1 = points[i][1]; for (int j = i + 1; j < N; j++) { int x2 = points[j][0]; int y2 = points[j][1]; int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2); adj.get(i).add(new int[]{dist, j}); adj.get(j).add(new int[]{dist, i}); } } int res = 0; Set<Integer> visit = new HashSet<>(); PriorityQueue<int[]> minH = new PriorityQueue<>( (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); minH.offer(new int[]{0, 0}); // {cost, point} while (visit.size() < N) { int[] top = minH.poll(); int cost = top[0]; int i = top[1]; if (visit.contains(i)) { continue; } res += cost; visit.add(i); for (int[] edge : adj.get(i)) { int neiCost = edge[0]; int nei = edge[1]; if (!visit.contains(nei)) { minH.offer(new int[]{neiCost, nei}); } } } return res;}
[cost, i]
—
res
0
visit
{}
heap size
1

Why it works

  1. Brute force tries every spanning tree. A complete graph on n points has nⁿ⁻² of them (Cayley), so that is hopeless past a handful of points.
  2. The cut property: split the points into "in the tree" and "not yet". The cheapest edge crossing that split belongs to some minimum spanning tree. Prim keeps every crossing edge in a min-heap and always takes the cheapest one.
  3. Cost: the graph is complete, so building adj is O(n²) edges, and each edge is pushed and popped at most once: O(n² log n) time, O(n²) space. A plain-array Prim without a heap gets O(n²).
  4. Pitfall: the heap keeps old entries for points already in the tree. Popping one must be skipped, or its cost gets added twice. That is the if (visit.contains(i)) continue; check.
  5. Alternative: Kruskal sorts all n² edges and adds each one that joins two different union-find sets. Same answer; Redundant Connection (684) uses the same union-find.