Cheapest Way to Connect All Points
You are given a list points, where points[i] = [x, y] is a point on a flat grid.
You can join any two points with a line. The cost of joining [x1, y1] and [x2, y2] is their Manhattan distance: |x1 - x2| + |y1 - y2|.
Choose lines so that every point is connected to every other point, directly or through other points. Return the smallest possible total cost.
Note
- With only one point, nothing needs to be joined, so the cost is
0. - All points are different.
Hint: this is a minimum spanning tree. Start from any point. At each step, add the point outside your group that is cheapest to join to any point inside it.
Examples
Example 1
- Input:
- [[0,0],[3,1],[5,5],[-2,4],[6,0]]
- Output:
- 20
Join [0,0]-[3,1] (cost 4), [3,1]-[6,0] (cost 4), [3,1]-[5,5] (cost 6) and [0,0]-[-2,4] (cost 6). Every point is now connected, and the total is 4 + 4 + 6 + 6 = 20. No cheaper set of lines connects all five points.
Example 2
- Input:
- [[7,-3]]
- Output:
- 0
There is only one point, so no line is needed.
Example 3
- Input:
- [[1,1],[1,4],[1,9]]
- Output:
- 8
The points are on one vertical line. Join [1,1]-[1,4] (cost 3) and [1,4]-[1,9] (cost 5). Total 8.
Constraints
1 <= points.length <= 30-100 <= x, y <= 100- All points are different.
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.