Skip to content

1584. Min Cost to Connect All Points

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|, where |val| denotes the absolute value of val.

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:

img

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

We can connect the points as shown above to get the minimum 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
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

Solution:

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;

        boolean[] inMST = new boolean[n];

        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>(){
                @Override
                public int compare(int[] edge1, int[] edge2){
                    if (edge1[2] < edge2[2]){
                        return -1;
                    }else if (edge1[2] > edge2[2]){
                        return 1;
                    }else{
                        return 0;
                    }
                }
            }
        );

        pq.offer(new int[]{0, 0, 0}); // {from to cost}
        int totalCost = 0;
        int edgesUsed = 0;

        // 当使用的边数小于点的数量时继续循环
        while(edgesUsed < n){ // n
            int[] cur = pq.poll();
            int to = cur[1];
            int cost = cur[2];

            // 如果该点已经包含在最小生成树中, 跳过
            if (inMST[to] == true){
                continue;
            }

            // 标记该点已经包含在最小生成树中
            inMST[to] = true;
            totalCost += cost; // 累加总代价
            edgesUsed++; // 增加已使用边的计数

            // 将新加入的点与所有未加入最小生成树的点之间的边加入堆中
            for (int next = 0; next < n; next++){ // n
                if (!inMST[next]){
                    int nextCost = Math.abs(points[to][0] - points[next][0]) +
                    Math.abs(points[to][1] - points[next][1]);

                    pq.offer(new int[]{to, next, nextCost}); // logn
                }
            }
        }

        return totalCost;
    }
}

// TC: O(n^2logn)
// SC: O(n^2)