← DSA Atlas
Dedicated problem page · #1584

Min Cost to Connect All Points

MediumShortest Path, Dijkstra and Minimum Spanning TreeMinimum spanning tree (Prim)Lazy Prim with a min-heap over Manhattan distances
Solve on LeetCode ↗
1584
MediumShortest Path, Dijkstra and Minimum Spanning TreeLazy Prim with a min-heap over Manhattan distancesMinimum spanning tree (Prim)

Min Cost to Connect All Points

Given n points on a 2D plane, the cost to connect two points is their Manhattan distance |xi-xj| + |yi-yj|. Return the minimum total cost to connect all points so that there is exactly one simple path between any two points.

Open official problem prompt ↗
In plain English

Wire together all points into one connected tree using the least total Manhattan wiring length.

Picture it like this

Laying cable between houses where cost is city-block distance: start at one house and keep extending to whichever unconnected house is nearest to the growing network.

Example
Input
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output
20
Why
The cheapest tree links (0,0)-(2,2)=4, (2,2)-(3,10)=9, (2,2)-(5,2)=3, (5,2)-(7,0)=4, summing to 20.
Constraints
1 <= points.length <= 1000-10^6 <= xi, yi <= 10^6All pairs (xi, yi) are distinct
Pattern lesson

See the pattern, then code

Minimum spanning tree (Prim)
Recognition clue

You must connect all points at minimum total edge weight on a complete graph where edge weights are computed on the fly - an MST problem best served by Prim's algorithm.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. The graph is implicitly complete, so rather than materialize all O(n^2) edges, grow the tree from one node, always adding the closest outside point via a heap.

New words, made simpleKnow these before the algorithm
Manhattan distance
Sum of absolute coordinate differences |dx| + |dy|, the grid-walking distance.
Prim's algorithm
Grows an MST one vertex at a time, always adding the cheapest edge leaving the current tree.
Implicit complete graph
Every pair of points is connectable, so edges are computed rather than stored.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Kruskal on all edges

Works but stores ~500k edges for n=1000, heavy on memory.

Generate all n(n-1)/2 edges, sort, and union with DSU.

Time O(n^2 log n)Space O(n^2)
Best choicePrim with a heap

Avoids materializing all edges and keeps memory linear.

Grow the tree from one node, pushing distances to outside nodes lazily.

Time O(n^2 log n)Space O(n)
The rule we keep true

Invariant

The set of included nodes always forms a subtree of some minimum spanning tree, and total holds its exact weight.

Why this is correct

Reasoning

Prim repeatedly applies the cut property: the lightest edge crossing from the current tree to the outside is always part of some MST. Growing the tree by that safe edge n-1 times yields a minimum spanning tree.

The algorithm in three movesSay these aloud before coding
1Start the tree with node 0 at distance 0

in_mst={0}, add (2,2) d=4 total=4

2Pop the minimum-distance node not yet in the tree from a min-heap

add (5,2) d=3 total=7

3Add its distance to the total and mark it included

add (7,0) d=4 total=11

4Push the Manhattan distance from the new node to every point still outside the tree

add (3,10) d=9 total=20

5Repeat until all n points are included

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0,0)0
(2,2)1
(3,10)2
(5,2)3
(7,0)4
1 · Readnode 0 (0,0)
2 · Askstart tree
3 · Update stateheap=[(0,0)], total=0
4 · ResultPop 0, in_mst={0}.
Key takeaway

Prim grows the tree from (0,0), each step attaching the nearest unconnected point by Manhattan distance.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-8State setup

    in_mst marks included points; the heap is seeded with node 0 at cost 0.

  2. 2
    Lines 9-14Pop and include

    Skip already-included pops (lazy deletion); otherwise add the edge cost and count the node.

  3. 3
    Lines 15-20Push outward edges

    From the newly added point, offer its Manhattan distance to every point still outside the tree.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single point needs 0 cost
  • Two points cost exactly their Manhattan distance
  • Large coordinate magnitudes still fit in Python ints without overflow
!

Common beginner mistakes

  • Forgetting the in_mst skip on pop, which would double-count nodes
  • Using Euclidean distance instead of Manhattan
  • Trying to precompute and store all O(n^2) edges, risking memory limits at n=1000
Check your understanding

Why does lazy Prim push a node multiple times into the heap, and is that a problem?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)