Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1584.html
1584. Min Cost to Connect All Points (Medium)
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
Example 3:
Input: points = [[0,0],[1,1],[1,0],[-1,1]] Output: 4
Example 4:
Input: points = [[-1000000,-1000000],[1000000,1000000]] Output: 4000000
Example 5:
Input: points = [[0,0]] Output: 0
Constraints:
1 <= points.length <= 1000
-106 <= xi, yi <= 106
- All pairs
(xi, yi)
are distinct.
Related Topics:
Union Find
Solution 1. Kruskal
The run time is too restrict. If you sort the edges then use Kruskal you will get TLE. The time complexity is O(N^2 * log(N^2))
.
We have to use min heap instead so that the time complexity is O(K * log(N^2))
where K
is the number of edges we need to scan to complete the tree. It’s much smaller than N^2
on average.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(K * log(N^2))
// Space: O(N^2)
// Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/discuss/843940/C%2B%2B-Minimum-Spanning-Tree-(Kruskal)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
--size;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int getSize() { return size; }
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
vector<array<int, 3>> E;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) E.push_back({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j });
}
make_heap(begin(E), end(E), greater<array<int, 3>>());
UnionFind uf(N);
while (uf.getSize() > 1) {
pop_heap(begin(E), end(E), greater<array<int, 3>>());
auto [w, u, v] = E.back();
E.pop_back();
if (uf.connected(u, v)) continue;
uf.connect(u, v);
ans += w;
}
return ans;
}
};
We can also directly use priority_queue
.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(K * log(N^2))
// Space: O(N^2)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
--size;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int getSize() { return size; }
};
class Solution {
typedef array<int, 3> Edge;
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) q.push({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j });
}
UnionFind uf(N);
while (uf.getSize() > 1) {
auto [w, u, v] = q.top();
q.pop();
if (uf.connected(u, v)) continue;
uf.connect(u, v);
ans += w;
}
return ans;
}
};
Solution 2. Prim
- Start from a random node (we use
0
here), add it to the minimum spanning tree (MST). - From all the edges connecting nodes in the MST and those outside of the MST, find the edge with the mimimal cost, and add the corresponding node to the MST.
- Repeat Step 2 until all the nodes are added into the MST.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/discuss/843921/PythonGolang-Just-add-points-greedily
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0, cur = 0;
vector<int> dist(N, INT_MAX), seen(N);
for (int i = 0; i < N - 1; ++i) {
int x = A[cur][0], y = A[cur][1];
seen[cur] = 1;
for (int j = 0; j < N; ++j) {
if (seen[j]) continue;
dist[j] = min(dist[j], abs(A[j][0] - x) + abs(A[j][1] - y));
}
cur = min_element(begin(dist), end(dist)) - begin(dist);
ans += dist[cur];
dist[cur] = INT_MAX;
}
return ans;
}
};
-
class Solution { public int minCostConnectPoints(int[][] points) { if (points == null || points.length <= 1) return 0; PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] array1, int[] array2) { return array1[2] - array2[2]; } }); int length = points.length; int[][] distances = new int[length][length]; for (int i = 0; i < length; i++) { int[] point1 = points[i]; for (int j = i + 1; j < length; j++) { int[] point2 = points[j]; int distance = manhattanDistance(point1, point2); priorityQueue.offer(new int[]{i, j, distance}); distances[i][j] = distance; distances[j][i] = distance; } } int[] parents = new int[length]; for (int i = 0; i < length; i++) parents[i] = i; int minCost = 0; int size = length; while (size > 1) { int[] array = priorityQueue.poll(); int index1 = array[0], index2 = array[1], distance = array[2]; if (find(parents, index1) != find(parents, index2)) { union(parents, index1, index2); minCost += distance; size--; } } return minCost; } public int manhattanDistance(int[] point1, int[] point2) { return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]); } public void union(int[] parents, int index1, int index2) { parents[find(parents, index1)] = find(parents, index2); } public int find(int[] parents, int index) { while (parents[index] != index) { parents[index] = parents[parents[index]]; index = parents[index]; } return index; } } ############ class Solution { private int[] p; public int minCostConnectPoints(int[][] points) { int n = points.length; List<int[]> g = new ArrayList<>(); for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = i + 1; j < n; ++j) { int x2 = points[j][0], y2 = points[j][1]; g.add(new int[] {Math.abs(x1 - x2) + Math.abs(y1 - y2), i, j}); } } g.sort(Comparator.comparingInt(a -> a[0])); p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } int ans = 0; for (int[] e : g) { int cost = e[0], i = e[1], j = e[2]; if (find(i) == find(j)) { continue; } p[find(i)] = find(j); ans += cost; if (--n == 1) { return ans; } } return 0; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } }
-
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/ // Time: O(K * log(N^2)) // Space: O(N^2) // Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/discuss/843940/C%2B%2B-Minimum-Spanning-Tree-(Kruskal) class UnionFind { vector<int> id; int size; public: UnionFind(int N) : id(N), size(N) { iota(begin(id), end(id), 0); } int find(int a) { return id[a] == a ? a : (id[a] = find(id[a])); } void connect(int a, int b) { int p = find(a), q = find(b); if (p == q) return; id[p] = q; --size; } bool connected(int a, int b) { return find(a) == find(b); } int getSize() { return size; } }; class Solution { public: int minCostConnectPoints(vector<vector<int>>& A) { int N = A.size(), ans = 0; vector<array<int, 3>> E; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) E.push_back({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j }); } make_heap(begin(E), end(E), greater<array<int, 3>>()); UnionFind uf(N); while (uf.getSize() > 1) { pop_heap(begin(E), end(E), greater<array<int, 3>>()); auto [w, u, v] = E.back(); E.pop_back(); if (uf.connected(u, v)) continue; uf.connect(u, v); ans += w; } return ans; } };
-
class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] g = [] n = len(points) for i, (x1, y1) in enumerate(points): for j in range(i + 1, n): x2, y2 = points[j] g.append((abs(x1 - x2) + abs(y1 - y2), i, j)) g.sort() p = list(range(n)) ans = 0 for cost, i, j in g: if find(i) == find(j): continue p[find(i)] = find(j) n -= 1 ans += cost if n == 1: return ans return 0
-
func minCostConnectPoints(points [][]int) int { n := len(points) var g [][]int for i, p := range points { x1, y1 := p[0], p[1] for j := i + 1; j < n; j++ { x2, y2 := points[j][0], points[j][1] g = append(g, []int{abs(x1-x2) + abs(y1-y2), i, j}) } } sort.Slice(g, func(i, j int) bool { return g[i][0] < g[j][0] }) ans := 0 p := make([]int, n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, e := range g { cost, i, j := e[0], e[1], e[2] if find(i) == find(j) { continue } p[find(i)] = find(j) ans += cost n-- if n == 1 { return ans } } return 0 } func abs(x int) int { if x < 0 { return -x } return x }