Min Cost to Connect All Points

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoft

Problem Description

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.

Examples

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⁶ ≤ xi, yi ≤ 10⁶
All pairs (xi, yi) are distinct.

Prim’s Algorithm for Minimum Spanning Tree (MST)

We want to find the Minimum Spanning Tree (MST) of a complete graph where vertices are points, and edge weights are Manhattan distances.

Prim’s algorithm builds the MST starting from an arbitrary node (say, index 0):

Maintain a visited set to track nodes in the tree, and a min-heap to store edges [cost, node], sorted by cost. Seed the heap with [0, 0].
While visited.size() < n:
- Pop the edge [cost, node] with the smallest cost.
- If node is already in the tree, skip it.
- Add node to visited, and add cost to our total MST sum.
- For all other nodes i not yet in visited:
  - Calculate Manhattan distance dist = abs(x1 - x2) + abs(y1 - y2).
  - Push [dist, i] to the heap.
Return the total MST sum.

Solution: Prim’s Algorithm

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        boolean[] visited = new boolean[n];
        // min-heap: [distance, nodeIndex]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[]{0, 0});

        int totalCost = 0;
        int edgesUsed = 0;

        while (edgesUsed < n) {
            int[] top = heap.poll();
            int cost = top[0], node = top[1];

            if (visited[node]) continue;

            visited[node] = true;
            totalCost += cost;
            edgesUsed++;

            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    int dist = Math.abs(points[node][0] - points[i][0])
                             + Math.abs(points[node][1] - points[i][1]);
                    heap.offer(new int[]{dist, i});
                }
            }
        }

        return totalCost;
    }
}

import heapq

class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        visited = [False] * n
        # min-heap: (distance, node_index)
        heap = [(0, 0)]
        
        total_cost = 0
        edges_used = 0

        while edges_used < n:
            cost, node = heapq.heappop(heap)
            
            if visited[node]:
                continue
                
            visited[node] = True
            total_cost += cost
            edges_used += 1

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

        return total_cost

#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

class Solution {
public:
    int minCostConnectPoints(std::vector<std::vector<int>>& points) {
        int n = points.size();
        std::vector<bool> visited(n, false);
        // min-heap: {distance, nodeIndex}
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> heap;
        heap.push({0, 0});

        int totalCost = 0;
        int edgesUsed = 0;

        while (edgesUsed < n) {
            auto [cost, node] = heap.top(); heap.pop();

            if (visited[node]) continue;

            visited[node] = true;
            totalCost += cost;
            edgesUsed++;

            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    int dist = std::abs(points[node][0] - points[i][0])
                             + std::abs(points[node][1] - points[i][1]);
                    heap.push({dist, i});
                }
            }
        }

        return totalCost;
    }
};

Complexity Analysis:

Time Complexity: O(N² log N) in the worst case since we push N edges onto the heap for each of the N visited nodes. (Because the graph is complete, Prim’s with a simple minimum-weight array instead of a heap can be optimized to O(N²), which is faster when the graph is dense).
Space Complexity: O(N²) worst-case heap size.