Sponsored
Sponsored
This approach involves treating the points as nodes of a graph and the Manhattan distance between them as the edge weights. The problem translates to finding a Minimum Spanning Tree (MST), which connects all nodes with the minimum edge weight.
Kruskal's algorithm is a popular choice for this kind of problem. It works as follows:
This approach efficiently computes the minimum cost of connecting all points.
The time complexity is dominated by the sorting step and the union-find operations. Sorting takes O(E log E), where E is the number of edges. Union-Find operations are nearly constant time, resulting in an overall complexity of O(E log E). The space complexity is O(n) for the Union-Find structure and edge storage, where n is the number of points.
1#include <vector>
2#include <algorithm>
3#include <cstdlib>
4using namespace std;
5
6class Solution {
7 struct Edge {
8 int point1;
9 int point2;
10 int weight;
11 };
12
int find(vector<int>& parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
void unionSets(vector<int>& parent, vector<int>& rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
vector<Edge> edges;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
edges.push_back({ i, j, dist });
}
}
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
vector<int> parent(n);
vector<int> rank(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
int minCost = 0;
int edgesUsed = 0;
for (const auto& edge : edges) {
if (find(parent, edge.point1) != find(parent, edge.point2)) {
unionSets(parent, rank, edge.point1, edge.point2);
minCost += edge.weight;
edgesUsed++;
if (edgesUsed == n - 1) {
break;
}
}
}
return minCost;
}
};Similar to the C solution, the C++ version employs a struct to represent edges and encapsulates the logic in a class. The Manhattan distance between each pair of points is computed, and the edges are sorted by distance. The graph is progressively built using a union-find data structure to keep track of connected components, adding the minimum edge to connect separate components. The overall algorithm returns the total minimum cost.
Another approach uses Prim's algorithm to construct the Minimum Spanning Tree (MST). Rather than sorting edges, Prim's method grows the MST one vertex at a time, starting from an arbitrary vertex and adding the minimum cost edge that expands the MST.
The steps involved are:
This approach offers a clear alternative to Kruskal's, particularly well-suited to densely connected systems.
This approach has a time complexity of O(n^2) due to nested loops over nodes, suitable for problems where n is moderately sized. Space complexity is O(n) for extra arrays managing node state and weights.
1import heapq
2
3class Solution:
4 def minCostConnectPoints(self, points):
5 n = len(points)
6 minDist = [float('inf')] * n
7 minDist[0] = 0
8 visited = [False] * n
9 heap = [(0, 0)] # (distance, point)
10 totalCost = 0
11
12 while heap:
13 cost, point = heapq.heappop(heap)
14 if visited[point]:
15 continue
16
17 visited[point] = True
18 totalCost += cost
19
20 for next_point in range(n):
21 if not visited[next_point]:
22 next_cost = abs(points[point][0] - points[next_point][0]) + abs(points[point][1] - points[next_point][1])
23 if next_cost < minDist[next_point]:
24 minDist[next_point] = next_cost
25 heapq.heappush(heap, (next_cost, next_point))
26
27 return totalCostThis Python solution uses a min-heap for Prim's algorithm, ensuring that the edge being considered is of the minimal weight at all times. It maintains arrays to track visited nodes and minimum weights for edges, updating and expanding the MST iteratively. The resulting solution provides the overall minimum cost to connect the set of given points.