forked from mdmzfzl/NeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1584-min-cost-to-connect-all-points.py
58 lines (46 loc) · 2.21 KB
/
1584-min-cost-to-connect-all-points.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
"""
Problem: LeetCode 1584 - Min Cost to Connect All Points
Key Idea:
The problem can be solved using Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph. We start by calculating the distances between all pairs of points and then sort these distances along with their corresponding pairs. We initialize an empty MST and iterate through the sorted distances. For each distance, we check if the two points belong to different connected components in the MST using Union-Find. If they do, we add the distance to the MST and merge the components. We continue this process until all points are connected.
Time Complexity:
- Calculating distances between all pairs takes O(n^2) time.
- Sorting the distances takes O(n^2 * log(n^2)) = O(n^2 * log n) time.
- Union-Find operations take nearly constant time (amortized), and we perform it n times.
- Therefore, the overall time complexity is dominated by sorting and is O(n^2 * log n).
Space Complexity:
- We store distances and the edges in O(n^2) space.
- Union-Find data structure uses O(n) space.
- Therefore, the space complexity is O(n^2).
"""
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
n = len(points)
distances = []
for i in range(n):
for j in range(i + 1, n):
distances.append((distance(points[i], points[j]), i, j))
distances.sort()
parent = list(range(n))
rank = [0] * n
mst_cost = 0
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(node1, node2):
root1 = find(node1)
root2 = find(node2)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
for distance, u, v in distances:
if find(u) != find(v):
union(u, v)
mst_cost += distance
return mst_cost