The problem
Given points [x, y], connecting two costs their Manhattan distance, |x₁ − x₂| + |y₁ − y₂| — the distance along a street grid.
Return the least total cost to connect all the points so that every point can reach every other along the connections.
Examples
- Input
points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
- Output
20
- Input
points = [[3, 12], [-2, 5], [-4, 1]]
- Output
18
Constraints
- 1 ≤ points.length ≤ 1000
- −10⁶ ≤ x, y ≤ 10⁶
- All points are different.
The idea
The cheapest set of connections that joins everything is a minimum spanning tree: n − 1 links and no loop, since a loop always has a link that can go.
Prim’s algorithm grows it from one point. Keep, for every point outside the tree, the cheapest link from it to any point inside. Each round, add the outside point with the cheapest link, then let it offer cheaper links to the rest. With every pair of points connectable, scanning the array of n costs each round (n² in all) beats sorting all n² / 2 possible links.
- Time
- O(n²)
- Space
- O(n)
Solution · every language run against every case
class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: # Prim's algorithm on the complete graph: grow one tree from point 0, always # adding the outside point that is cheapest to connect to it. n = len(points) cost = [float("inf")] * n # cheapest link from each outside point to the tree cost[0] = 0 inside = [False] * n total = 0 for _ in range(n): u = min((i for i in range(n) if not inside[i]), key=lambda i: cost[i]) inside[u] = True total += cost[u] for v in range(n): # u may offer a cheaper link to the points still outside if not inside[v]: d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]) cost[v] = min(cost[v], d) return total