Min Cost to Connect All Points
- 2 min read
- Graph
- LC-Medium
- Binary-heap
3 years ago
Solution
- Use Prim's Algorithm for Minimum Spanning Tree, kinda like a Breadth-first Search
- Assume each point is connected to every other point: first make adjacency list containing distances from each node to all other nodes
- Next, start from point at index 0, and look at min heap to get next point with shortest point. Initially we add all neighbors from index 0 to heap, and subsequently add neighbours to heap
- Whenever we visit a node, we immediately all nodes visitable from current node to the min heap.
- At any point in time, all paths leaving the nodes we already visited must be in the heap.
- Remember that cycles are not allowed in Minimum Spanning Trees, so use a visited set
- Keep doing algorithm until we've visited all nodes
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def minCostConnectPoints(self, points: List[List[int]]) -> int:
adj = defaultdict(list)
for i in range(len(points)):
for j in range(i + 1, len(points)):
x1, y1 = points[i]
x2, y2 = points[j]
dist = abs(x1 - x2) + abs(y1 - y2)
adj[i].append((dist, j))
adj[j].append((dist, i))
total_cost = 0
heap = [val for val in adj[0]]
heapify(heap)
vis = set()
vis.add(0)
while len(vis) < len(points):
next_cost, next_point = heappop(heap)
if next_point not in vis:
vis.add(next_point)
for cost, point in adj[next_point]:
if point not in vis:
heappush(heap, (cost, point))
total_cost += next_cost
return total_cost