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. Connect (0,0) and (2,2) with cost 4.
2. Connect (2,2) and (5,2) with cost 3.
3. Connect (5,2) and (7,0) with cost 5.
4. Connect (7,0) and (3,10) with cost 14. Total minimum cost = 4 + 3 + 5 + 8 = 20

Example 2

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

Steps

1. Calculate the distances: Compute the Manhattan distance between all pairs of points. This forms a complete graph.
2. Minimum Spanning Tree (MST): We need to find the Minimum Spanning Tree (MST) of this complete graph. Prim's algorithm or Kruskal's algorithm are suitable for this. Prim's algorithm is used in the solution below.
3. Prim's Algorithm:
   • Start with an arbitrary node and mark it as visited.
   • Repeatedly add the edge with the minimum weight connecting a visited node and an unvisited node.
   • Continue until all nodes are visited. The sum of the edge weights in the MST is the minimum cost.

Explanation

The problem is essentially finding the minimum spanning tree of a complete graph where nodes represent points and edge weights are the Manhattan distances between them. Prim's algorithm efficiently solves this. We maintain a priority queue (min-heap) to quickly find the edge with the minimum weight connecting a visited node to an unvisited node.

Code (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // for numeric_limits

using namespace std;

int manhattanDistance(pair<int, int> p1, pair<int, int> p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    if (n <= 1) return 0; // Base case: no edges needed

    // priority queue to store edges (weight, u, v)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

    // set to keep track of visited nodes
    vector<bool> visited(n, false);

    //initializing with distance from 0 to every node
    for(int i = 1; i < n; ++i){
        pq.emplace(manhattanDistance(points[0], points[i]), 0, i);
    }
    visited[0] = true;
    int minCost = 0;
    int edges = 0;

    while(edges < n-1){
        auto [weight, u, v] = pq.top();
        pq.pop();

        if(visited[v]) continue;

        minCost += weight;
        visited[v] = true;
        edges++;

        for(int i = 0; i < n; ++i){
            if(!visited[i]){
                pq.emplace(manhattanDistance(points[v], points[i]), v, i);
            }
        }
    }
    return minCost;
}

int main() {
    vector<vector<int>> points1 = {{0,0},{2,2},{3,10},{5,2},{7,0}};
    cout << "Minimum cost for Example 1: " << minCostConnectPoints(points1) << endl; // Output: 20

    vector<vector<int>> points2 = {{3,12},{-2,5},{-4,1}};
    cout << "Minimum cost for Example 2: " << minCostConnectPoints(points2) << endl; // Output: 18

    return 0;
}

Complexity

• Time Complexity: O(N^2 log N), where N is the number of points. This is dominated by the priority queue operations in Prim's algorithm. Building the initial priority queue is O(N^2) and each extraction and insertion is O(log N).
• Space Complexity: O(N), primarily for the visited array and the priority queue. The priority queue can hold up to N edges in the worst case.