LeetCode 1584 · Advanced Graphs

Min Cost to Connect All Points, explained with a picture

Laying the cheapest cables between houses.

MediumAdvanced Graphs
▶ Watch it step by step

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

  1. 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.
  2. 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.
  3. 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.
  4. Use a heap of offers. When house i joins, push (distance, j) for every house j not yet connected: an offer to connect j through i. The heap pops the cheapest offer.
  5. 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 and continue ignores it.
  6. 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 cost

LeetCode 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

ApproachTimeSpace
Brute forceO(C(E, n − 1)·n): every choice of n − 1 cables is testedO(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: heappush and heappop come from heapq.

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 done check, 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.
Your turn: cables of limited length

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.

Check what stuck

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?

2. Why does the shown code skip a popped house with if i in done: continue?

3. A learner deletes the lines if i in done: and continue. Which input now returns a wrong cost?

Score 60% or more and the lesson is marked complete.