DSA problem
Min Cost to Connect All Points
You are given an array points where points[i] = [xi, yi] describes a point on a 2D plane. The cost of connecting two points (xi, yi) and (xj, yj) is the Manhattan distance between them, that is |xi - xj| + |yi - yj|. Return the minimum total cost to make all the points connected, where all points are connected if there is exactly one simple path between every pair of points.
This is a classic Minimum Spanning Tree (MST) problem on an implicit complete graph: every pair of points is an edge whose weight is the Manhattan distance between them. With n points the graph has n * (n - 1) / 2 edges, so the algorithm should avoid materialising all of them when possible.
Two canonical MST algorithms apply. Kruskal's sorts every edge by weight and accepts each edge that joins two distinct components using a Disjoint Set Union (DSU) — this costs O(E log E) where E = n^2. Prim's, on the other hand, grows the tree from a starting vertex by repeatedly extracting the cheapest edge that leaves the visited set, which suits a dense graph because edges can be generated on the fly.
The optimal approach for this problem is Prim's with a min-heap. Start at any vertex (say index 0), push its edges to all other vertices into a priority queue keyed by cost, then repeatedly pop the cheapest edge whose other endpoint is still unvisited, mark it visited, accumulate its cost, and push all edges from the newly added vertex. The algorithm terminates after adding n - 1 edges, giving O(n^2 log n) time and O(n^2) space worst case — fast in practice and trivial to implement.
Examples
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]20points = [[3,12],[-2,5],[-4,1]]18points = [[0,0]]0Constraints
- 1 <= points.length <= 1000
- -10^6 <= xi, yi <= 10^6
- All pairs (xi, yi) are distinct.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.