Problem
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.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Constraints:
1 <= points.length <= 1000
-106 <= xi, yi <= 106
All pairs
(xi, yi)
are distinct.
Solution
/**
* @param {number[][]} points
* @return {number}
*/
var minCostConnectPoints = function(points) {
var edges = [];
for (var i = 0; i < points.length; i++) {
for (var j = i + 1; j < points.length; j++) {
edges.push([i, j, getDistance(points, i, j)]);
}
}
edges.sort((a, b) => a[2] - b[2]);
var res = 0;
var parents = Array(points.length).fill(0).map((_, i) => i);
var rank = Array(points.length).fill(0);
for (var m = 0; m < edges.length; m++) {
var [i, j, distance] = edges[m];
var n = find(parents, i);
var k = find(parents, j);
if (n === k) continue;
if (rank[n] <= rank[k]) {
union(parents, n, k);
rank[k]++;
} else {
union(parents, k, n);
rank[n]++;
}
res += distance;
}
return res;
};
var getDistance = function(points, i, j) {
return Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
};
var union = function(parents, i, j) {
parents[i] = j;
};
var find = function(parents, i) {
if (parents[i] === i) {
return i;
}
parents[i] = find(parents, parents[i]);
return parents[i];
};
Explain:
Union-find to detect circle.
Kruskal’s Algorithm to get minimum spanning tree.
Complexity:
- Time complexity : O(n ^ 2).
- Space complexity : O(n ^ 2).