Leetcode 1584: Min Cost to Connect All Points
You are given a list of points on a 2D plane, represented as coordinates [x, y]. The cost of connecting two points is defined by the Manhattan distance, which is calculated as |xi - xj| + |yi - yj|. Your task is to return the minimum total cost required to connect all the points. A valid connection between points must form a connected graph, where there is exactly one simple path between any two points.
Problem
Approach
Steps
Complexity
Input: You are given an array of points, where each point is represented by a pair of integers: [xi, yi]. The length of the array is at least 1 and at most 1000.
Example: Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Constraints:
• 1 <= points.length <= 1000
• -10^6 <= xi, yi <= 10^6
• All pairs (xi, yi) are distinct.
Output: Return the minimum cost to connect all the points such that the graph formed by the connections is a connected graph with one simple path between any two points.
Example: Output: 20
Constraints:
• The output should be an integer value representing the minimum connection cost.
Goal: The goal is to calculate the minimum cost of connecting all the points using a Minimum Spanning Tree (MST) approach.
Steps:
• 1. Create a list of all possible point connections, each with its corresponding Manhattan distance.
• 2. Sort the connections in increasing order of distance.
• 3. Use a union-find data structure to efficiently group connected points.
• 4. Add connections to the MST, ensuring no cycles are formed, until all points are connected.
Goal: The number of points can be large (up to 1000), so an efficient solution is necessary.
Steps:
• 1 <= points.length <= 1000
• -10^6 <= xi, yi <= 10^6
• All pairs of points are distinct.
Assumptions:
• The points are given in integer coordinates.
• Manhattan distance is used to calculate the cost between two points.
• All points are distinct.
• Input: Input: points = [[3,12],[-2,5],[-4,1]]
• Explanation: In this case, we need to connect three points on a 2D plane. The cost of connecting them is minimized by choosing the optimal connections, leading to a total cost of 18.
Approach: This problem can be approached using Kruskal's algorithm for Minimum Spanning Tree (MST), where we calculate the distances between all pairs of points, sort them, and progressively build the MST while ensuring no cycles are formed.
Observations:
• We need to efficiently calculate and store the Manhattan distances between all pairs of points.
• To avoid cycles, we can use a union-find or disjoint-set data structure.
• The solution involves sorting the pairwise distances and using the union-find data structure to add edges progressively.
Steps:
• 1. Calculate the Manhattan distances between all pairs of points.
• 2. Sort the distances and store the pair indices.
• 3. Implement a union-find data structure to manage connected components.
• 4. Iterate over the sorted distances, connecting the points and adding the distances to the total cost.
Empty Inputs:
• Ensure that the algorithm handles the case when there's only one point (the cost should be 0).
Large Inputs:
• The algorithm should handle large numbers of points efficiently, particularly when points are spread across a large area.
Special Values:
• Handle edge cases where all points are collinear, or form an easily calculable minimal spanning tree.
Constraints:
• Ensure the solution works within the provided time and space constraints.
static bool cmp(array<int, 3> &a, array<int, 3> &b) {
return a[0] < b[0];
}
int minCostConnectPoints(vector<vector<int>>& pts) {
vector<array<int, 3>> q;
// priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
for(int i = 0; i < pts.size(); i++) {
for(int j = i + 1; j < pts.size(); j++)
q.push_back({ abs(pts[i][0]-pts[j][0]) + abs(pts[i][1]-pts[j][1]), i, j});
}
sort(q.begin(), q.end(), cmp);
UF* uf = new UF(pts.size());
int cost = 0, n = pts.size();
for(int i = 0; i < q.size(); i++) {
// cout << uf->cnt << " " << q[0] << " " << q[1] << " " << q[2] << "\n";
if(uf->uni(q[i][1], q[i][2])) {
// cout << n << " "<< cost << " " << q[i][0] << " " << q[i][1] << " " << q[i][2] << "\n";
cost += q[i][0];
n--;
if(n == 1) return cost;
}
}
return 0;
}
1 : Helper Function
static bool cmp(array<int, 3> &a, array<int, 3> &b) {
This function is a comparison function for sorting. It compares two arrays based on the first element, which represents the distance between two points.
2 : Comparison Logic
return a[0] < b[0];
This line returns true if the first element of array `a` (the distance) is less than that of array `b`, which allows sorting of pairs based on distance.
3 : Function Declaration
int minCostConnectPoints(vector<vector<int>>& pts) {
The main function `minCostConnectPoints` takes a 2D vector `pts` representing the points' coordinates and returns the minimum cost to connect all points.
4 : Variable Initialization
vector<array<int, 3>> q;
We initialize a vector `q` of arrays, where each array contains the cost (distance between two points) and the indices of the two points.
5 : Outer Loop
for(int i = 0; i < pts.size(); i++) {
We start a loop to iterate through all the points in the `pts` vector.
6 : Inner Loop
for(int j = i + 1; j < pts.size(); j++)
This inner loop iterates through all points after the current point `i` to calculate distances between pairs of points.
7 : Push Distance to Vector
q.push_back({ abs(pts[i][0]-pts[j][0]) + abs(pts[i][1]-pts[j][1]), i, j});
For each pair of points, we calculate the Manhattan distance and store it along with the indices of the points in the vector `q`.
8 : Sort Distances
sort(q.begin(), q.end(), cmp);
Sort the vector `q` based on the distances between points using the `cmp` function defined earlier.
9 : Union-Find Initialization
UF* uf = new UF(pts.size());
Initialize a union-find (disjoint-set) structure to manage the connected components of points.
10 : Cost and Points Count Initialization
int cost = 0, n = pts.size();
Initialize `cost` to 0 and `n` to the number of points. `cost` will accumulate the minimum cost, and `n` tracks the number of disconnected components.
11 : Loop Over Sorted Distances
for(int i = 0; i < q.size(); i++) {
We loop over the sorted distances in `q` to process the smallest distances first.
12 : Union Operation
if(uf->uni(q[i][1], q[i][2])) {
If the two points represented by `q[i][1]` and `q[i][2]` are in different components, we unite them.
13 : Update Cost
cost += q[i][0];
Add the cost (distance) of the current edge (pair of points) to the total `cost`.
14 : Decrement Components Count
n--;
Decrement the number of disconnected components. As two points are connected, the number of components reduces.
15 : Terminate Early
if(n == 1) return cost;
If only one component remains, all points are connected, and we return the total `cost`.
16 : Return Result
return 0;
Return 0 if the function did not find a valid minimum spanning tree (though this should not happen in typical use).
Best Case: O(n^2 log n) - The time complexity depends on the number of points and sorting the pairwise distances.
Average Case: O(n^2 log n)
Worst Case: O(n^2 log n)
Description: The dominant factor is the sorting of pairwise distances, which is O(n^2 log n).
Best Case: O(n) - In the case where no distances need to be stored, the space complexity can be O(n).
Worst Case: O(n^2) - Storing all pairwise distances requires O(n^2) space.
Description: The space complexity is driven by the storage of pairwise distances.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus