Skip to content
AI360Xpert
Back to Advanced Graphs
Medium

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.

Examples

Input:points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output:20
We can connect the points as follows: (0,0) to (2,2) with cost 4 (2,2) to (5,2) with cost 3 (5,2) to (7,0) with cost 4 (2,2) to (3,10) with cost 9 Total cost = 4 + 3 + 4 + 9 = 20. This connects all points with the minimum cost.
Input:points = [[3,12],[-2,5],[-4,1]]
Output:18
Connect (-4,1) to (-2,5) with cost 6. Connect (-2,5) to (3,12) with cost 12. Total cost = 18.

Constraints

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

Prim's Algorithm (Minimum Spanning Tree)

Approach

We need to find the Minimum Spanning Tree (MST) of the graph where nodes are points and edge weights are Manhattan distances. We can use Prim's algorithm: 1. Start with any node (e.g., node 0) and add it to the MST. 2. Keep a priority queue of edges (cost, target_node) that connect the MST to nodes not yet in the MST. 3. Repeatedly extract the minimum cost edge. If the target node is not in the MST, add it to the MST, add the cost to the total, and push all its outgoing edges to unvisited nodes into the priority queue. 4. Stop when all nodes are in the MST.

Complexity Analysis

Time Complexity
O(n^2 log n)
Space Complexity
O(n^2)

In a complete graph, the number of edges is O(n^2). Each edge operation on the min-heap takes O(log(n^2)) = O(log n) time. So the time complexity is O(n^2 log n). Space complexity is O(n^2) for the priority queue.

Solution.java
class Solution {    public int minCostConnectPoints(int[][] points) {        int n = points.length;        // Min-heap to store (cost, node)        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);        boolean[] visited = new boolean[n];                minHeap.offer(new int[]{0, 0});        int res = 0;        int connected = 0;                while (connected < n) {            int[] curr = minHeap.poll();            int cost = curr[0];            int i = curr[1];                        if (visited[i]) {                continue;            }                        visited[i] = true;            res += cost;            connected++;                        for (int j = 0; j < n; j++) {                if (!visited[j]) {                    int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);                    minHeap.offer(new int[]{dist, j});                }            }        }                return res;    }}