Min Cost to Connect All Points medium

Problem Statement

You are given an array points where points[i] = [xi, yi] represents the coordinates of the ith point on a 2D plane. The cost of connecting two points points[i] and points[j] is the manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to connect all points such that there is a 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 follows:

1. (0,0) -> (2,2) : cost = 4
2. (2,2) -> (5,2) : cost = 3
3. (5,2) -> (7,0) : cost = 5
4. (7,0) -> (3,10) : cost = 10 + 8 = 18 Total cost = 4 + 3 + 5 + 8 = 20

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

Steps to Solve

This problem is a classic Minimum Spanning Tree (MST) problem. We can use Prim's algorithm or Kruskal's algorithm to solve it efficiently. Here's a solution using Prim's algorithm:

1. Calculate Distances: Compute the Manhattan distance between every pair of points. This forms a complete graph.
2. Prim's Algorithm:
   • Initialize a minHeap (priority queue) with the first point. The heap will store edges (represented as [cost, point1, point2]). The cost is the distance between point1 and point2.
   • Initialize a visited set to keep track of visited points.
   • While the visited set doesn't contain all points:
     • Extract the edge with the minimum cost from the minHeap.
     • If the destination point of the edge hasn't been visited:
       • Add the destination point to the visited set.
       • Add edges from the destination point to all other unvisited points to the minHeap.
   • The sum of the costs of the edges added to the MST is the minimum cost.

Explanation

Prim's algorithm greedily builds the MST by repeatedly adding the edge with the minimum cost that connects a visited vertex to an unvisited vertex. The use of a min-heap ensures that the minimum cost edge is always considered first. This approach guarantees finding the minimum spanning tree because it iteratively selects the cheapest edges that avoid cycles.

Code (Java)

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); //Cost, u, v
        Set<Integer> visited = new HashSet<>();
        int minCost = 0;

        // Add edges from the first point to all other points.
        for(int i = 1; i < n; i++){
            int cost = Math.abs(points[0][0] - points[i][0]) + Math.abs(points[0][1] - points[i][1]);
            minHeap.offer(new int[]{cost, 0, i});
        }
        visited.add(0);


        while(visited.size() < n){
            int[] edge = minHeap.poll();
            int cost = edge[0];
            int u = edge[1];
            int v = edge[2];

            if(visited.contains(v)) continue;

            minCost += cost;
            visited.add(v);

            //Add edges from v to unvisited points
            for(int i = 0; i < n; i++){
                if(!visited.contains(i)){
                    int newCost = Math.abs(points[v][0] - points[i][0]) + Math.abs(points[v][1] - points[i][1]);
                    minHeap.offer(new int[]{newCost, v, i});
                }
            }
        }
        return minCost;
    }
}

Complexity

• Time Complexity: O(N^2 log N), where N is the number of points. This is dominated by the heap operations in Prim's algorithm. Building the initial heap takes O(N) and each extraction takes O(log N). We do this N times.
• Space Complexity: O(N), mainly for the visited set and the minHeap. The heap size will be at most N in the worst case.