Min Cost to Connect All Points
You are given points in the plane. The cost of connecting two points is their Manhattan distance. Return the minimum total cost to connect all points so that every pair is linked by some path.
- 1 ≤ points.length ≤ 1000
- -10^6 ≤ x, y ≤ 10^6
- All points distinct
- Connect all nodes at minimum total cost = minimum spanning tree
- Complete graph — every pair is a candidate edge
- Sort edges and add those that join different components
When connectivity is built up incrementally by unions and queried repeatedly, disjoint sets with path compression and union by rank answer both in near-constant amortized time, without rebuilding anything. It is the right tool whenever DFS would have to be rerun after each new edge, and it is the engine of Kruskal's MST.
Generate all n(n-1)/2 edges with their Manhattan weights and sort them. Process edges in increasing weight with a disjoint-set structure: if the endpoints are in different sets, union them and add the weight to the total; stop after n - 1 edges are accepted. This is Kruskal's algorithm; the cut property guarantees each accepted edge belongs to some MST.
- Prim's algorithm with a plain array (no heap) runs in O(n^2) time and O(n) space, which is better for this dense complete graph.