LeetCode #1584 Medium

Min Cost to Connect All Points

Connect every point with minimum total Manhattan edge cost.

graphminimum-spanning-treeprim

02

Intuition

Choosing each point's cheapest neighbor can create disconnected clusters or cycles. Treat points as vertices of a complete weighted graph, where Manhattan distance is the edge weight. Connecting all vertices for minimum total weight is exactly a minimum spanning tree. Prim's algorithm grows one connected component by repeatedly taking its cheapest crossing edge.

How to spot this pattern

Whenever all locations must be connected and edge costs are additive, consider a minimum spanning tree. A dense implicit graph often favors Prim's algorithm because edges can be generated as vertices enter the tree.

03

Approach

1

Begin Prim's frontier at the first point

Put (0, 0) in a min-heap: point zero can enter the tree for no cost. Track visited points so a vertex contributes to the total only on its first removal.

2

Accept the cheapest edge crossing into an unseen point

Pop the minimum pair, skip it if its endpoint is already visited, otherwise add its cost and mark the point. The cut property guarantees this cheapest frontier edge is safe for an MST.

3

Expose Manhattan edges from each accepted point

Compute distances from the newly visited point to every unvisited point and push them into the heap. Stop after n vertices have joined; stale alternatives may remain in the heap but cannot change the tree.

04

Solution

▶1class Solution:
▶2    def minCostConnectPoints(self, points: List[List[int]]) -> int:
▶3        n = len(points)
▶4        heap = [(0, 0)]
▶5        visited = set()
▶6        total = 0
▶7 
▶8        while len(visited) < n:
▶9            cost, point = heappop(heap)
▶10            if point in visited:
▶11                continue
▶12            visited.add(point)
▶13            total += cost
▶14            x1, y1 = points[point]
▶15            for neighbor, (x2, y2) in enumerate(points):
▶16                if neighbor not in visited:
▶17                    distance = abs(x1 - x2) + abs(y1 - y2)
▶18                    heappush(heap, (distance, neighbor))
▶19        return total

05

Common pitfalls

Adding costs for stale heap entries

✗ Wrong

cost, point = heappop(heap)
total += cost

✓ Right

cost, point = heappop(heap)
if point in visited:
    continue
total += cost

Multiple candidate edges can lead to the same vertex, but an MST accepts it only once.

Using Euclidean distance

✗ Wrong

distance = sqrt(dx * dx + dy * dy)

✓ Right

distance = abs(dx) + abs(dy)

The problem explicitly assigns Manhattan edge costs.

Stopping when the heap first empties incorrectly

✗ Wrong

while heap and len(visited) < n - 1:

✓ Right

while heap and len(visited) < n:

All n vertices, including the starting point, must be accepted.

06

Edge cases

Only one point

The initial zero-cost entry visits it and the result remains zero.

Several heap entries target the same point

The visited check accepts only the cheapest first entry and discards stale ones.

Negative coordinates

Absolute coordinate differences compute Manhattan distance without special handling.

07

Complexity

Time

O(n^2 log n)

Space

O(n^2)

This direct Prim implementation may retain many candidate edges for the complete graph.