Min Cost to Connect All Points

Difficulty: Medium Source: NeetCode

Problem

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

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

Example 2: Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

Constraints:

• 1 <= points.length <= 1000
• -10^6 <= xi, yi <= 10^6
• All pairs (xi, yi) are distinct

Prerequisites

Before attempting this problem, you should be comfortable with:

• Minimum Spanning Tree (MST) — a tree connecting all nodes with minimum total edge weight
• Prim’s Algorithm — greedy MST algorithm starting from a single node
• Kruskal’s Algorithm — MST by sorting edges and adding them greedily
• Union-Find — data structure for tracking connected components

1. Prim’s Algorithm

Intuition

This is a classic Minimum Spanning Tree problem. Every pair of points has an edge with cost equal to Manhattan distance, so we have a complete graph. We want the subset of edges that connects all points with minimum total cost — that’s the MST.

Prim’s algorithm builds the MST by starting from any node and greedily adding the cheapest edge that connects a new node to the current tree. We use a min-heap to always find the cheapest edge efficiently.

Algorithm

1. Start from point 0. Mark it as visited.
2. Push all edges from point 0 to the heap.
3. While not all points are in the MST:
   • Pop the cheapest edge (cost, next_point).
   • If next_point is already visited, skip.
   • Add cost to the total. Mark next_point as visited.
   • Push all edges from next_point to unvisited points into the heap.
4. Return total cost.

Solution

import heapq

def minCostConnectPoints_prim(points):
    n = len(points)
    visited = set()
    heap = [(0, 0)]  # (cost, point_index)
    total = 0

    while len(visited) < n:
        cost, i = heapq.heappop(heap)
        if i in visited:
            continue
        visited.add(i)
        total += cost

        for j in range(n):
            if j not in visited:
                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                heapq.heappush(heap, (dist, j))

    return total


print(minCostConnectPoints_prim([[0,0],[2,2],[3,10],[5,2],[7,0]]))  # 20
print(minCostConnectPoints_prim([[3,12],[-2,5],[-4,1]]))             # 18
print(minCostConnectPoints_prim([[0,0],[1,1],[1,0],[-1,1]]))         # 4

Complexity

• Time: O(n² log n) — each of n² edges can be pushed/popped from the heap
• Space: O(n²) — heap can hold all edges

2. Kruskal’s Algorithm with Union-Find

Intuition

Kruskal’s takes a different approach: generate all possible edges, sort them by cost, then greedily add edges from cheapest to most expensive — but only if the two endpoints aren’t already connected (checked via Union-Find). Stop when all points are in one component.

Both Prim’s and Kruskal’s give the same MST weight, but Kruskal’s is more natural when you already have the edge list. Here we generate all n*(n-1)/2 edges upfront.

Algorithm

1. Generate all pairs of points and compute Manhattan distances.
2. Sort edges by distance.
3. Initialize Union-Find with n components.
4. For each edge (cost, i, j) in sorted order:
   • If i and j are in different components, union them and add cost.
   • Stop when we’ve added n-1 edges (MST is complete).
5. Return total cost.

Solution

def minCostConnectPoints_kruskal(points):
    n = len(points)

    # Union-Find
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    # Generate all edges
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((dist, i, j))

    edges.sort()

    total = 0
    edges_used = 0
    for cost, i, j in edges:
        if union(i, j):
            total += cost
            edges_used += 1
            if edges_used == n - 1:
                break

    return total


print(minCostConnectPoints_kruskal([[0,0],[2,2],[3,10],[5,2],[7,0]]))  # 20
print(minCostConnectPoints_kruskal([[3,12],[-2,5],[-4,1]]))             # 18
print(minCostConnectPoints_kruskal([[0,0],[1,1],[1,0],[-1,1]]))         # 4
print(minCostConnectPoints_kruskal([[0,0]]))                            # 0

Complexity

• Time: O(n² log n) — generating O(n²) edges and sorting them
• Space: O(n²) — edge list

Common Pitfalls

Forgetting that it’s a complete graph. Every point connects to every other point — you don’t need a predefined edge list. Compute Manhattan distances on the fly.

Double-counting edges in Kruskal’s. When generating pairs (i, j), only iterate j from i+1 to avoid adding each edge twice.

Stopping Prim’s too early. Check len(visited) < n, not len(visited) <= n. The loop should run until all n points are added.