Min Cost to Connect All Points - LeetCode

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.

- code #Prim

```
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def dis(pi, pj):
return abs(pi[0] - pj[0]) + abs(pi[1] - pj[1])
cost = 0
n = len(points)
visited = [False] * n
cur = 0 # start from point 0
unconnected = n - 1 # point 0 as connected and visited
visited[0] = True
pq = []
heapq.heapify(pq)
while unconnected > 0:
for point in range(n):
if not visited[point]: # from current, to every unvisited point
heapq.heappush(pq, (dis(points[cur], points[point]), point))
while pq:
shortest, j = heapq.heappop(pq)
if not visited[j]: # j is the shortest unvisited point
break
unconnected -= 1
cost += shortest
visited[j] = True
cur = j # update to next round
return cost
```

- code #Prim shorter, optimized

```
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def dis(pi, pj):
return abs(pi[0] - pj[0]) + abs(pi[1] - pj[1])
cost = 0
n = len(points)
visited = set()
pq = [[0, 0]] # (distance, current point)
while len(visited) < n:
shortest, cur = heapq.heappop(pq)
if cur in visited: continue
visited.add(cur)
cost += shortest
for point in range(n):
if point not in visited: # from current, to every unvisited point
heapq.heappush(pq, (dis(points[cur], points[point]), point))
return cost
```

- code #Kruskal #unionfind

```
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
root = [i for i in range(n)]
rank = [1] * n
def find(x):
if x != root[x]:
root[x] = find(root[x])
return root[x]
def union(x, y):
rtx = find(x)
rty = find(y)
if rtx == rty: return False
rkx = rank[rtx]
rky = rank[rty]
if rkx > rky:
root[rty] = rtx
elif rkx < rky:
root[rtx] = rty
else:
root[rty] = rtx
rank[rtx] += 1
return True
def dis(px, py):
return abs(px[0] - py[0]) + abs(px[1] - py[1])
dis_pq = []
for i in range(n-1):
for j in range(i+1, n):
dis_pq.append((dis(points[i], points[j]), i, j)) # put all edges
heapq.heapify(dis_pq)
res = 0
while n - 1 > 0:
cur_dis, i, j = heapq.heappop(dis_pq)
if union(i, j): # if can connect, means not already connected, not a cycle
res += cur_dis
n -= 1
return res
```