Min Cost to Connect All Points
Problem
You are given points on a 2D plane. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all points so that every pair is linked by some path.
Examples
Constraints
- • 1 <= points.length <= 1000
- • -10^6 <= xi, yi <= 10^6
- • All points are distinct
Hints & approach
Hint 1
Treat the points as a complete graph with Manhattan-distance weights.
Hint 2
The cheapest way to connect every node is a minimum spanning tree.
Hint 3
On a dense graph, Prim's algorithm with an O(n) scan per step avoids building all edges.
Approachtry the hints first
Run Prim's algorithm. Keep, for every point not yet in the tree, the cheapest known cost to attach it (initially infinity, and 0 for the start). Repeatedly pick the unattached point with the smallest cost, add that cost to the total, and relax every other unattached point using its distance to the newly added one. With the array-scan version this is O(n^2) time and O(n) space, which beats sorting all n^2 edges for Kruskal.
Time O(n^2) · Space O(n)