Min Cost to Connect All Points

Problem

You are given n points on a 2D integer grid, points[i] = [x, y], all distinct. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the minimum total cost of a set of connections such that every point can reach every other point through the connections (directly or via other points).

• Up to about a thousand points on the grid.
• Coordinates fit comfortably in a normal int, positive or negative.
• No two points coincide.

Examples

• points = [[1,1],[4,3],[6,12],[9,2],[12,5]] → 28. Connect (1,1)-(4,3) for 5, (4,3)-(9,2) for 6, (9,2)-(12,5) for 6, and (4,3)-(6,12) for 11.
• points = [[5,15],[-3,6],[-6,1]] → 25. Two connections: (5,15)-(-3,6) costs 17 and (-3,6)-(-6,1) costs 8.
• points = [[2,2]] → 0. One point needs no connections.

Hints

1. Any connected set of n points with no redundant connections is a tree with n - 1 edges. What is the classic name for the cheapest such tree?
2. Grow the tree one point at a time: always attach the closest not-yet-connected point. Why is that greedy choice never wrong?
3. Prim's algorithm on the complete graph; because every pair is an edge, an O(n²) array-based Prim without a heap is the best fit.