634. Min Cost to Connect All Points
You are given points, an array of distinct positions on a 2D grid, where points[i] = [xi, yi]. Laying a wire between two points costs their Manhattan distance: |xi - xj| + |yi - yj|.
Return the minimum total wiring cost that leaves every point reachable from every other point (directly or through intermediate points). In other words: pick a set of wires of smallest total cost that connects all the points into one network — in the cheapest network every pair of points is linked by one and only one route, since extra wires only add cost.
Your function receives the array of [x, y] pairs and returns one integer, the minimum total cost.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: Wire (0,0)-(2,2) costs 4, (2,2)-(5,2) costs 3, (5,2)-(7,0) costs 4, and (2,2)-(3,10) costs 9. Every point is now connected and 4 + 3 + 4 + 9 = 20 is the cheapest possible total.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Explanation: Connect (3,12)-(-2,5) for 12 and (-2,5)-(-4,1) for 6. Total 18 — cheaper than any set of wires that includes the direct (3,12)-(-4,1) link of cost 18 plus anything else.
Constraints:
- 1 ≤ points.length ≤ 1000
- -10⁶ ≤ xi, yi ≤ 10⁶
- All pairs (xi, yi) are distinct.
Hints:
The points and possible wires form a complete weighted graph: n nodes and an edge between every pair. "Cheapest set of edges that connects everything" is the definition of a minimum spanning tree (MST).
Kruskal's algorithm: generate all n(n-1)/2 edges, sort by weight, and take an edge whenever its endpoints are in different components — a union-find (disjoint set) with path compression answers that in near-constant time. Stop after n-1 edges.
For a dense complete graph, Prim's algorithm with a plain distance array is even better: keep minDist[v] = cheapest wire from the growing tree to v, absorb the closest outside point, and relax the array. O(n²) time, O(n) space — no edge list at all.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Expected output: 20