Min Cost to Connect All Points
Last Updated: April 5, 2026
Understanding the Problem
This problem is asking us to find the Minimum Spanning Tree (MST) of a complete graph. Each point is a node, and the edge weight between any two nodes is their Manhattan distance. We want to connect all nodes with the minimum total edge cost, using exactly n-1 edges (where n is the number of points).
The fact that the problem says "exactly one simple path between any two points" is another way of saying "build a tree that spans all nodes." In graph theory, that is an MST.
So the real question becomes: how do we efficiently find the MST of a complete graph with up to 1000 nodes? With n points, there are n*(n-1)/2 possible edges, which for n=1000 means about 500,000 edges. Two classic algorithms handle this well: Kruskal's and Prim's.
Key Constraints:
1 <= points.length <= 1000→ With n up to 1000, we have up to ~500,000 edges. O(n^2) is 10^6, which is comfortable. O(n^2 log n) is also fine. This means both Kruskal's and Prim's will work.-10^6 <= xi, yi <= 10^6→ Coordinates can be large, so Manhattan distances can be up to 4 * 10^6. We need int (not short) to store edge weights.All pairs are distinct→ No duplicate points, so every edge has a positive weight.
Approach 1: Kruskal's Algorithm (Sort Edges + Union-Find)
Intuition
The most natural way to think about building an MST: list every possible edge, sort them by cost, and greedily pick the cheapest edge that connects two components that aren't already connected. This is Kruskal's algorithm.
For this problem, each pair of points forms an edge with weight equal to their Manhattan distance. With n points, we get n*(n-1)/2 edges. We sort all edges by weight, then iterate through them. For each edge, if the two endpoints belong to different connected components, we include the edge and merge the components. We stop once we've added n-1 edges.
The key data structure here is Union-Find (also called Disjoint Set Union). It lets us check "are these two points in the same component?" and "merge these two components" both in nearly O(1) amortized time using path compression and union by rank.
Algorithm
- Generate all possible edges: for every pair of points (i, j), compute the Manhattan distance and store it as an edge (cost, i, j).
- Sort all edges by cost in ascending order.
- Initialize a Union-Find structure with n nodes.
- Iterate through the sorted edges. For each edge, if the two endpoints are in different components, union them and add the edge cost to the total.
- Stop once we've added n-1 edges (the tree is complete).
- Return the total cost.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). Generating all edges takes O(n^2). Sorting them takes O(n^2 log n) since there are n^2/2 edges. Processing each edge with Union-Find is nearly O(1) amortized. The sorting step dominates.
- Space Complexity: O(n^2). We store all n^2/2 edges explicitly, plus O(n) for the Union-Find arrays.
This approach works but stores and sorts all n*(n-1)/2 edges upfront. What if we grew the tree one node at a time, only looking at edges to unvisited nodes?
Approach 2: Prim's Algorithm (Min-Heap)
Intuition
Instead of sorting all edges upfront, Prim's algorithm grows the MST one node at a time. Start from any node, and at each step, pick the cheapest edge that connects a node already in the tree to a node not yet in the tree.
Prim's algorithm relies on the cut property of MSTs: the cheapest edge crossing any cut between "in-tree" and "not-in-tree" nodes must be part of the MST. The min-heap efficiently gives us the cheapest crossing edge at each step.
We never need to see all edges at once. As the tree grows, old candidate edges to newly visited nodes become irrelevant and are lazily discarded when popped from the heap.
Algorithm
- Start with node 0 in the MST. Push all edges from node 0 to the heap.
- Mark node 0 as visited.
- While we have fewer than n nodes in the MST:
- Pop the cheapest edge from the heap.
- If the target node is already visited, skip it.
- Otherwise, add it to the MST, add the edge cost to the total, and push all edges from the new node to unvisited nodes.
- Return the total cost.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). Each of the n nodes gets added to the tree once. When a node is added, we push up to n edges to the heap. The heap can grow to O(n^2) entries, so each operation is O(log n). Total: O(n^2 log n).
- Space Complexity: O(n^2). The heap can contain up to O(n^2) entries in the worst case.
The heap accumulates duplicate entries for the same node, bloating it to O(n^2) size. What if we tracked the minimum edge cost to each unvisited node directly in an array?
Approach 3: Optimized Prim's (No Heap)
Intuition
For dense graphs like this one (where every pair of nodes has an edge), using a heap actually hurts. The heap grows to O(n^2) entries, and each operation is O(log n). A simpler approach: maintain an array minDist where minDist[j] is the cheapest edge from any node in the MST to node j.
At each step, scan the minDist array to find the unvisited node with the smallest distance. Add it to the tree, then update minDist for all remaining unvisited nodes. This is O(n) per step, and we do n-1 steps, giving O(n^2) total.
Algorithm
- Initialize
minDist[j] = Manhattan distance from point 0 to point jfor all j. SetminDist[0] = -1to mark node 0 as visited (in the MST). - Repeat n-1 times:
- Find the unvisited node
uwith the smallestminDist[u]. - Add
minDist[u]to the total cost. - Mark
uas visited by settingminDist[u] = -1. - For every unvisited node
v, updateminDist[v] = min(minDist[v], Manhattan distance from u to v). - Return the total cost.
Example Walkthrough
Code
- Time Complexity: O(n^2). The outer loop runs n-1 times. Inside, finding the minimum takes O(n) and updating distances takes O(n). Total: O(n) * O(n) = O(n^2). This is optimal since we need to consider all n^2 edges at least once.
- Space Complexity: O(n). Only the minDist array of size n. No heap, no edge list.