AlgoMaster Logo

Min Cost to Connect All Points

mediumFrequency7 min readUpdated June 23, 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

Kruskal's algorithm builds the MST by listing every possible edge, sorting them by cost, and greedily picking the cheapest edge that connects two components that aren't already connected.

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. Adding the cheapest edge that joins two separate components is safe because of the cut property: across any partition of the nodes, the minimum-weight edge crossing that partition belongs to some MST, so we never regret taking it.

Union-Find (also called Disjoint Set Union) handles the component bookkeeping. It checks whether two points are in the same component and merges two components, both in nearly O(1) amortized time using path compression and union by rank.

Algorithm

  1. Generate all possible edges: for every pair of points (i, j), compute the Manhattan distance and store it as an edge (cost, i, j).
  2. Sort all edges by cost in ascending order.
  3. Initialize a Union-Find structure with n nodes.
  4. 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.
  5. Stop once we've added n-1 edges (the tree is complete).
  6. Return the total cost.

Example Walkthrough

1Sorted edges: (1,3)=3, (0,1)=4, (3,4)=4, (0,3)=7, (0,4)=7, (1,4)=7, (1,2)=9, (2,3)=10, (0,2)=13, (2,4)=14
0
3
edge
1
4
2
4
3
7
4
7
5
7
6
9
7
10
8
13
9
14
1/6

Code

Kruskal's stores and sorts all n*(n-1)/2 edges upfront. The next approach grows the tree one node at a time and only looks at edges leading 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.

Algorithm

  1. Start with node 0 in the MST. Push all edges from node 0 to the heap.
  2. Mark node 0 as visited.
  3. 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.
  4. Return the total cost.

Example Walkthrough

1Start: add node 0 to MST. Push edges to heap. Total=0
0
true
1
false
2
false
3
false
4
false
1/5

Code

The heap accumulates duplicate entries for the same node, growing to O(n^2) size. The next approach replaces the heap with an array that tracks the cheapest edge cost to each unvisited node.

Approach 3: Optimized Prim's (No Heap)

Intuition

For a dense graph like this one, where every pair of nodes has an edge, the heap costs more than it saves. It grows to O(n^2) entries with O(log n) per operation, which is O(n^2 log n) overall. The graph already forces us to look at all n^2 edges, so the log n factor on top is pure overhead.

Instead, maintain an array minDist where minDist[j] is the cheapest edge from any node already in the MST to node j. At each step, scan minDist to find the unvisited node with the smallest distance, add it to the tree, then update minDist for every remaining unvisited node. Each step is O(n), and there are n-1 steps, for O(n^2) total. That linear scan replaces the heap's O(log n) extract-min, removing the log factor.

Algorithm

  1. Initialize minDist[j] = Manhattan distance from point 0 to point j for all j. Set minDist[0] = -1 to mark node 0 as visited (in the MST).
  2. Repeat n-1 times:
    • Find the unvisited node u with the smallest minDist[u].
    • Add minDist[u] to the total cost.
    • Mark u as visited by setting minDist[u] = -1.
    • For every unvisited node v, update minDist[v] = min(minDist[v], Manhattan distance from u to v).
  3. Return the total cost.

Example Walkthrough

1Initialize from node 0: minDist = distances from node 0. Total=0
0
-1
1
4
min=4
2
13
3
7
4
7
1/5

Code