Minimum Cost to Connect All Points

Share

Connect all points with minimum total Manhattan distance cost (MST problem).

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

Solution Approach

Prim's algorithm: greedily add the closest unvisited point to the MST.

  • Use min-heap of (cost, point_index)
  • Start with point 0, cost 0
  • While not all points visited: pop min cost point
  • Add to MST, add all edges to unvisited points to heap
  • Return total cost
Java
public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
    pq.offer(new int[]{0, 0});
    int cost = 0, count = 0;
    while (count < n) {
        int[] cur = pq.poll();
        if (visited[cur[1]]) continue;
        visited[cur[1]] = true;
        cost += cur[0];
        count++;
        for (int j = 0; j < n; j++) {
            if (!visited[j]) {
                int d = Math.abs(points[cur[1]][0]-points[j][0]) + Math.abs(points[cur[1]][1]-points[j][1]);
                pq.offer(new int[]{d, j});
            }
        }
    }
    return cost;
}
  • Time Complexity: O(n^2 log n)
  • Space Complexity: O(n^2)