Min Cost to Connect All Points
You are given an array of points where points[i] = [xi, yi] is a point on the X-Y plane. You need to find the minimum cost to connect all points.
Constraints:
- 1 <= points.length <= 1000
- points[i].length == 2
- 0 <= xi, yi <= 10^4
Examples:
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: The minimum cost to connect all points is 20. One possible way to connect the points is: (0,0) -> (2,2) -> (3,10) -> (5,2) -> (7,0). The total cost is |2-0| + |2-0| + |3-2| + |10-2| + |5-3| + |2-10| + |7-5| + |0-2| = 20.
Solutions
Kruskal's Algorithm
This solution uses Kruskal's algorithm to find the minimum spanning tree of the graph. The graph is represented as a set of edges, where each edge is a pair of points and the weight of the edge is the Manhattan distance between the two points. The algorithm sorts the edges by weight and then iterates over the sorted edges, adding each edge to the minimum spanning tree if it does not form a cycle with the edges already in the tree. The union-find data structure is used to keep track of the connected components of the graph.
def minCostConnectPoints(points):
n = len(points) edges = [] for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) edges.append([dist, i, j]) edges.sort(key=lambda x:
x[0]) parent = list(range(n)) rank = [0] * n cost = 0 for dist, u, v in edges:
rootU = find(parent, u) rootV = find(parent, v) if rootU != rootV:
union(parent, rank, rootU, rootV) cost += dist return cost
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) return parent[x]
def union(parent, rank, x, y):
rootX = find(parent, x) rootY = find(parent, y) if rank[rootX] < rank[rootY]:
parent[rootX] = rootY elif rank[rootX] > rank[rootY]:
parent[rootY] = rootX else:
parent[rootY] = rootX rank[rootX] += 1Follow-up:
How would you modify the solution to handle the case where the points are not in the X-Y plane, but in a higher-dimensional space?
