Min Cost to Connect All Points (LeetCode 1584)

The problem

You get n points on a 2-D plane. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all the points, so that there is a path between every pair.

Input:  points = [[0,0], [2,2], [3,10], [5,2], [7,0]]
Output: 20

Connect (0,0)–(2,2) for 4, (2,2)–(5,2) for 3, (5,2)–(7,0) for 4 and (2,2)–(3,10) for 9. The total is 20, and no cheaper set of links connects everything.

How to think about it

Start with brute force. Every pair of points could be linked, so there are n(n−1)/2 candidate edges. Trying every subset of edges that connects all points is exponential.

The key insight: this is a minimum spanning tree. “Connect every node with the smallest total edge weight” is exactly the definition of an MST. The cheapest connected network never has a cycle (you could drop the most expensive edge of the cycle and stay connected), so it is a tree with n − 1 edges. Two classic algorithms build it: Kruskal’s (sort all edges, add them with union-find) and Prim’s (grow one tree outward).

Why Prim’s here. The graph is complete: every point links to every other, so there are about n²/2 edges. Prim’s fits well. Start from any point. Repeatedly add the cheapest edge that connects a point in the tree to a point outside it. The cut property guarantees this greedy choice is always part of some MST. A min-heap of (distance, point) keeps the cheapest crossing edge on top.

Which pattern is this? Minimum spanning tree with Prim’s. The tell is “connect everything at minimum total cost”, with no source or destination.

Approach

1. Push (0, 0) onto a min-heap: point 0 joins the tree at cost 0.
2. Pop the cheapest entry (d, i). If i is already in the tree, skip it (a stale, more expensive edge).
3. Otherwise add i to the tree, add d to the total, and count it.
4. Push the distance from i to every point not yet in the tree.
5. Stop when all n points are in the tree and return the total.

Solution

import heapq
def minCostConnectPoints(points):
    n = len(points); visited = [False] * n; h = [(0, 0)]; total = 0; cnt = 0
    while cnt < n:
        d, i = heapq.heappop(h)                 # cheapest edge leaving the tree
        if visited[i]: continue                 # already joined via a cheaper edge
        visited[i] = True; total += d; cnt += 1
        for j in range(n):
            if not visited[j]:
                dist = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])
                heapq.heappush(h, (dist, j))
    return total
# minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]]) -> 20

Dry run

Points are numbered 0 to 4 in input order.

All five points are in the tree, so the answer is 20.

Complexity

• Time: O(n² log n). Each of the n points pushes up to n edges, so the heap sees O(n²) entries at log cost each. An array-based Prim’s (keep the best distance for each point, scan for the minimum) runs in O(n²) with no heap.
• Space: O(n²). The heap can hold that many stale entries.

Edge cases and pitfalls

• One point costs 0: the loop adds it at cost 0 and stops.
• Duplicate points have distance 0 and are joined for free.
• Using Euclidean distance is a common slip; read the cost definition.
• Dijkstra is the wrong tool. It minimises distance from one source, not the total weight of the network.
• Kruskal’s works too, but sorting all n² edges costs O(n² log n) time and O(n²) memory up front.

Related problems

• Redundant Connection (LeetCode 684): union-find, the engine behind Kruskal’s MST.
• Network Delay Time (LeetCode 743): the same heap-driven growth, but Dijkstra minimises path length instead.
• Number of Connected Components (LeetCode 323): checking connectivity, the property an MST guarantees.