Min Cost to Connect All Points

Problem

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

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
Explanation:
We can connect the points as shown to get the minimum total cost of 20.
Notice that there is a unique path between every pair of points.

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.

Solution

Approach 1: Prim’s Algorithm (Greedy MST)

The key insight is this is a Minimum Spanning Tree (MST) problem. Prim’s algorithm greedily adds the minimum cost edge connecting visited and unvisited nodes.

Implementation

import heapq

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        def manhattan(i, j):
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

        # Start from point 0
        visited = set([0])
        min_heap = []

        # Add all edges from point 0
        for j in range(1, n):
            cost = manhattan(0, j)
            heapq.heappush(min_heap, (cost, j))

        total_cost = 0

        while len(visited) < n:
            cost, point = heapq.heappop(min_heap)

            if point in visited:
                continue

            # Add this point to MST
            visited.add(point)
            total_cost += cost

            # Add all edges from new point to unvisited points
            for next_point in range(n):
                if next_point not in visited:
                    next_cost = manhattan(point, next_point)
                    heapq.heappush(min_heap, (next_cost, next_point))

        return total_cost

Approach 2: Kruskal’s Algorithm (Union-Find)

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        def manhattan(i, j):
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

        # Generate all edges
        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                cost = manhattan(i, j)
                edges.append((cost, i, j))

        # Sort edges by cost
        edges.sort()

        # Union-Find
        parent = list(range(n))

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            root_x, root_y = find(x), find(y)
            if root_x == root_y:
                return False
            parent[root_x] = root_y
            return True

        total_cost = 0
        edges_used = 0

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

        return total_cost

Complexity Analysis

Prim’s Algorithm:

Time Complexity: O(N² log N), where N is number of points. We may add O(N²) edges to heap.
Space Complexity: O(N²) for the heap in worst case.

Kruskal’s Algorithm:

Time Complexity: O(N² log N), where N is number of points. Sorting N² edges dominates.
Space Complexity: O(N²) for storing all edges.

Key Insights

Minimum Spanning Tree: Connecting all points with minimum cost is the classic MST problem.
Complete Graph: Every point can connect to every other point, creating a complete graph with N² edges.
Manhattan Distance: The cost function is Manhattan distance, but the algorithm works with any cost function.
Prim’s Greedy: Prim’s algorithm grows the MST one vertex at a time, always adding the minimum cost edge.
Kruskal’s Union-Find: Kruskal’s processes edges in order of cost, using Union-Find to avoid cycles.
N-1 Edges: A spanning tree of N nodes has exactly N-1 edges, which both algorithms respect.