1. Min Cost to Connect All Points (LeetCode)
Model answer
The task
Given points in a plane, connect them so every point is reachable from every other point, minimizing the total Manhattan distance of the chosen connections.
Key idea
The points form a complete weighted graph, but explicitly building all edges is unnecessary. Prim’s algorithm can grow a minimum spanning tree by tracking each unconnected point’s cheapest connection to the current tree.
Approach
- Start the tree at point
0with cost0. - Keep the cheapest known connection cost for each point and mark points as visited when added.
- Repeatedly add the unvisited point with the smallest connection cost.
- Add that cost to the answer, then update the remaining costs using Manhattan distance from the newly added point.
- Return the sum after all points have been added.
from typing import List
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 1:
return 0
# best[i] is the cheapest edge currently known from the tree to i.
best = [float("inf")] * n
best[0] = 0
visited = [False] * n
total_cost = 0
for _ in range(n):
# Select the unvisited point with the cheapest connection.
current = -1
for i in range(n):
if not visited[i] and (
current == -1 or best[i] < best[current]
):
current = i
visited[current] = True
total_cost += best[current]
x1, y1 = points[current]
for i in range(n):
if not visited[i]:
x2, y2 = points[i]
distance = abs(x1 - x2) + abs(y1 - y2)
best[i] = min(best[i], distance)
return total_cost
Complexity:
- Time: O(n²), from selecting the next point and updating distances for each point.
- Space: O(n), for the connection costs and visited flags.
Common follow-ups
- Can Kruskal’s algorithm solve it? Yes; generate all point pairs, sort by distance, and use Union-Find, taking O(n² log n) time and O(n²) space.
- Can Prim’s algorithm use a heap? Yes, but this dense graph still has O(n²) possible edges; the array-based version is simpler and avoids storing them.
- What if there is only one point? No connection is needed, so the cost is
0. - What if distances use another metric? Replace the Manhattan distance calculation, provided the edge weights remain well-defined.