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.
SOLUTION:
import heapq
from collections import defaultdict
class Solution:
def union(self, parent, i, j):
parent[i] = j
def getParent(self, parent, i):
if i not in parent:
return i
return self.getParent(parent, parent[i])
def isCycle(self, graph, n):
parent = {}
for i in graph:
for j in graph[i]:
x = self.getParent(parent, i)
y = self.getParent(parent, j)
if x == y:
return True
self.union(parent, x, y)
return False
def minCostConnectPoints(self, points):
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
a, b = points[i]
c, d = points[j]
cost = abs(c - a) + abs(d - b)
heapq.heappush(edges, (cost, i, j))
graph = defaultdict(set)
rem = n - 1
op = 0
while rem > 0:
if len(edges) > 0:
currdist, i, j = heapq.heappop(edges)
graph[i].add(j)
if self.isCycle(graph, n):
graph[i].remove(j)
else:
rem -= 1
op += currdist
return op
Top comments (0)