You are given points, where points[i] = [x, y] is a point on a 2D plane. Connecting two points costs their Manhattan distance abs(x1 - x2) + abs(y1 - y2). Return the minimum total cost to connect all points so that there is exactly one simple path between any two of them.
- 1 <= points.length <= 1000
- -10^6 <= x, y <= 10^6
- All points are distinct
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force over all spanning trees is impossible. This is a classic MST. Kruskal needs all n^2 / 2 edges sorted, which is O(n^2 log n) time and O(n^2) memory. Because the graph is dense, array-based Prim is better: grow the tree from point 0, keep for each outside point the cheapest distance to any tree point, add the closest one, and refresh distances using only the newly added point. Each of the n rounds is O(n), so O(n^2) total and O(n) memory.
Algorithm
- Create
bestfilled with infinity, setbest[0] = 0, and aninTreearray of false. - Repeat
ntimes: pick the pointunot in the tree with the smallestbest[u]. - Add
best[u]to the total and markuas in the tree. - For every point
vnot in the tree, setbest[v] = min(best[v], dist(u, v)). - Return the total.
O(n^2)Space: O(n)class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: n = len(points) best = [float('inf')] * n # cheapest edge from the tree to each point best[0] = 0 in_tree = [False] * n total = 0 for _ in range(n): u = -1 for i in range(n): if not in_tree[i] and (u == -1 or best[i] < best[u]): u = i in_tree[u] = True total += best[u] ux, uy = points[u] for v in range(n): if not in_tree[v]: d = abs(ux - points[v][0]) + abs(uy - points[v][1]) if d < best[v]: best[v] = d return total