Min Cost to Connect All Points
MediumGraphs
You are given points, where points[i] = [x_i, y_i] is a point with integer coordinates; all points are distinct. The cost of connecting two points is their Manhattan distance, |x_i - x_j| + |y_i - y_j|.
Choose connections so that every point can reach every other point, either directly or through other points. Return the minimum total cost of such a set of connections. A single point needs no connections, so its cost is 0.
Example 1
- Input:
- points = [[0, 0], [2, 1], [3, 4], [5, 1]]
- Output:
- 10
- Explanation
- Connect
[2,1]to[0,0](cost 3), to[5,1](cost 3) and to[3,4](cost 4), for a total of 10. Every other pair is at least 5 apart, so no cheaper set of three connections exists.
Example 2
- Input:
- points = [[0, 0], [1, 1], [1, 0], [-1, 1]]
- Output:
- 4
- Explanation
[1,0]connects to both[0,0]and[1,1]at cost 1 each, and[-1,1]is 2 away from[0,0], giving 1 + 1 + 2 = 4.
Example 3
- Input:
- points = [[7, -3]]
- Output:
- 0
- Explanation
- There is only one point, so nothing needs to be connected.
Constraints
1 <= points.length <= 1000-10^6 <= x_i, y_i <= 10^6- All points are distinct