🌱 Keegan's Digital Garden

1584. Min Cost to Connect All Points

2 min read

📝 Problem Details

input array points where points[i] = [x,y] representing coordinates on a plot the cost of connecting two points is the Manhattan distance between them Manhattan Distance = abs(xi - xj) + abs(yi - yj) return the minimum cost to make

💭What Were My Initial Thoughts?

- Since we are looking for the the minimum weight of edges to connect all vertices, this indicates a minimum spanning tree problem:
- Kruskals or Prims?
	- both can work, but lets go with Prim's since its better for dense graphs

💡 Explanation of Solution

Prims Algorithm:
- use a priority queue (min-heap) to always pick the smallest edge
- maintain a minDist array where minDist[i] stores the minimum cost to connect point i
- start from any node
- keep adding the smallest edge (greedy approach) until all points are connected
- the sum of the edge cost gives the minimum spanning tree cost

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> minDist(n, INT_MAX); // store min distance to MST
        vector<bool> inMST(n, false); // track visited nodes
 
        int totalCost = 0;
        int edgesUsed = 0;
 
        // min-heap {distance, point index}
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.push({0,0}); // start from point 0
 
        while(edgesUsed < n) {
            auto[cost, u] = pq.top();
            pq.pop();
 
            if(inMST[u]) continue; // skip if already included
 
            // add this point to MST
            inMST[u] = true;
            totalCost += cost;
            edgesUsed++;
 
            // update minDist for remaining points
            for(int v = 0; v < n; v++) {
                if(!inMST[v]) {
                    int weight = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                    if (weight < minDist[v]) {
                        minDist[v] = weight;
                        pq.push({weight, v});
                    }
                }
            }
        }
        return totalCost;
    }
};

Graph View