The problem
Given points on a grid, connect them all with cables. A cable between two points costs their Manhattan distance |x1 − x2| + |y1 − y2|. Find the minimum total cost to connect every point.
Input: houses (0,0) (2,2) (3,10) (5,2) (7,0) Output: 20
Picture it
Picture houses on a street grid that all need internet. We start with one house connected. Each round we add the cheapest cable that reaches a house not yet connected (cables run along the streets, so their length is Δx + Δy). Once every house is connected, the cables form the cheapest network.
How to recognise it
- You must connect every point to the others using the cheapest total cable, and cables can run between any two points.
- The answer is a tree touching all points: n − 1 cables and no loop, because a loop wastes a cable.
- The cost of linking two points is a simple formula (Manhattan distance), so every pair is a possible edge.
- With up to 1,000 points there are about 500,000 possible cables, so you need something close to O(n²), not exponential.
Start with brute force
Try every choice of n − 1 cables out of all possible ones, keep those that connect everything without a loop, and take the cheapest.
from itertools import combinations
def min_cost_brute(points):
n = len(points)
def d(p, q):
return abs(p[0] - q[0]) + abs(p[1] - q[1])
edges = [(d(points[a], points[b]), a, b)
for a, b in combinations(range(n), 2)]
def is_tree(es):
parent = list(range(n))
def find(x):
while parent[x] != x:
x = parent[x]
return x
for a, b in es:
ra, rb = find(a), find(b)
if ra == rb:
return False
parent[rb] = ra
return True
best = None
for combo in combinations(edges, n - 1):
if is_tree([(a, b) for _, a, b in combo]):
cost = sum(c for c, _, _ in combo)
if best is None or cost < best:
best = cost
return best if best is not None else 0
There are n(n − 1)/2 possible cables and C(E, n − 1) ways to pick n − 1 of them. For just 10 points that is C(45, 9) = 886,163,135 combinations; for 1,000 points it is astronomically many. Space is O(E).
From brute force to the idea
- Find the waste. Almost all combinations are not trees, and the rest differ in small ways, yet each one is built and priced from scratch.
- Grow one tree. Start with house 0. At every step, add the cheapest cable that links a new house to the houses already connected. This is Prim's algorithm.
- Why greedy is safe. For any group of connected houses, the cheapest cable leaving that group belongs to some cheapest overall network, so taking it never rules out an optimal answer.
- Use a heap of offers. When house
ijoins, push(distance, j)for every housejnot yet connected: an offer to connectjthroughi. The heap pops the cheapest offer. - Skip stale offers. A house can have several offers in the heap. The first one popped is the cheapest, so when a popped house is already in
done, the offer is old andcontinueignores it. - Add up the costs. Each accepted offer's distance is added to
cost. The loop ends when all n houses are connected.
The key idea: always buy the cheapest cable that reaches a house you have not connected yet.
The key idea
Prim’s algorithm for a minimum spanning tree: grow from one point, always taking the cheapest edge to a new point.
Python solution
def min_cost_connect(points):
n, done, cost = len(points), set(), 0
heap = [(0, 0)] # (cable length, house)
while len(done) < n:
d, i = heappop(heap)
if i in done:
continue
done.add(i); cost += d
for j in range(n):
if j not in done:
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
heappush(heap, (dist, j))
return costLeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(C(E, n − 1)·n): every choice of n − 1 cables is tested | O(E): the list of all cables |
| Prim with a heap (shown code) | O(n² log n): about n²/2 offers are pushed in total, each push and pop costs O(log n) | O(n²) for the heap of offers, plus O(n) for done |
For n = 1,000 this means about 500,000 pushes. A version that keeps an array of best-known distances instead of a heap runs in O(n²) time and O(n) space.
Edge cases
- One point (
[[0,0]]): returns 0, since no cable is needed. - Identical points (
[[1,1],[1,1],[1,1]]): returns 0, because the cables have length 0. - Two points (
[[0,0],[-3,4]]): returns 7, their Manhattan distance. - Negative coordinates are fine, since distances use absolute values.
- An empty list: returns 0.
- Imports:
heappushandheappopcome fromheapq.
Common mistakes
- Using Dijkstra's shortest-path tree, which minimises each house's distance from the start, not the total cable.
- Adding the distance from house 0 to each house instead of the cable that connects it to the tree.
- Forgetting the
if i in donecheck, which counts stale offers and gives too large a cost. - Building only the cables to house 0 and assuming that is enough.
- Using Euclidean distance when the problem specifies Manhattan distance.
Cables longer than a limit L cannot be laid. Return the minimum total cost to connect all points using only cables of length at most L, or -1 if that is impossible. Describe what changes, then write it if you like.
Compare with our answer
Same Prim's algorithm, but do not push offers that are too long. The heap may now run empty before every house is connected, so check that, and report -1 if some houses were never reached.
def min_cost_limited(points, L):
n, done, cost = len(points), set(), 0
heap = [(0, 0)]
while heap and len(done) < n:
d, i = heappop(heap)
if i in done:
continue
done.add(i)
cost += d
for j in range(n):
if j not in done:
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
if dist <= L:
heappush(heap, (dist, j))
return cost if len(done) == n else -1
For the four points [[0,0],[2,0],[2,3],[5,3]], a limit of 2 gives -1 and limits of 3 or more give 8. Time O(n² log n), space O(n²).
A strong answer mentions: filtering offers by length, the loop condition now needing the heap to be non-empty, and returning -1 when not everything was connected.
1. A town lists candidate roads between villages, each with a building cost. You must pick roads so that all villages are linked, at the lowest total cost. Which approach fits best?
This is a minimum spanning tree, which Kruskal's method builds greedily with union-find. A shortest-path tree minimises distances from the source, not the total cost, and a DFS tree ignores costs.
2. Why does the shown code skip a popped house with if i in done: continue?
Each time a house joins the tree it pushes an offer for every unconnected house, so one house can appear many times. The first pop is the cheapest offer, and any later offer for it is old.
3. A learner deletes the lines if i in done: and continue. Which input now returns a wrong cost?
Stale offers get counted when they pop before the loop is finished. On the last input the answer comes out as 7 instead of 5. In the smaller inputs every stale offer is popped only after all houses are connected, so the cost is right.
Score 60% or more and the lesson is marked complete.