You are given points, a list of distinct [x, y] integer coordinates. Joining two points costs their Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost so that every point is reachable from every other (directly or through other points).
Implement min_cost_connect_points(points: list[list[int]]) -> int.
min_cost_connect_points([[0, 0], [3, 0], [3, 4]]) # 7 (3 + 4)
min_cost_connect_points([[5, 5]]) # 0
min_cost_connect_points([[1, 1], [2, 5], [6, 2]]) # 11 (5 + 6)
Constraints: 1 <= len(points) <= 1000, coordinates in [-10^6, 10^6].
Every pair of points can be joined, so there are about n²/2 possible links; aim for O(n²) or O(n² log n).
Show hint
you want the cheapest set of links that connects everything, which never needs a cycle. On a graph where every pair is linked, growing one connected tree by repeatedly adding the cheapest link from the tree to a point outside it needs only an O(n) array of "cheapest link so far", no heap and no edge list.