Min Cost to Connect All Points
Part of Practice: Shortest & Cheapest
You are given points on a 2D grid, each as [x, y]. Connecting two points costs their Manhattan distance — |x1 - x2| + |y1 - y2|, the distance walking only along grid lines. Return the minimum total cost of wires needed so that every point is connected to every other point, directly or through intermediate points.
Constraints that matter: up to 1000 points, so the complete graph has up to ~500,000 possible edges — an O(n²) algorithm over points is fine, but building and sorting every edge is wasteful.
Examples
- Input:
- points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
- Output:
- 20
Connect [0,0]-[2,2] (cost 4), [2,2]-[5,2] (cost 3), [5,2]-[7,0] (cost 4), and [2,2]-[3,10] (cost 9). Total 20, and every point can reach every other.
- Input:
- points = [[3,12],[-2,5],[-4,1]]
- Output:
- 18
Connect [3,12]-[-2,5] (cost 12) and [-2,5]-[-4,1] (cost 6).
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.