Advanced Graphs Minimum spanning trees
485. Min Cost to Connect All Points
You are given a list of points on a plane, where points[i] = [x, y]. You can connect any two points, and
connecting [x1, y1] with [x2, y2] costs their Manhattan distance, |x1 - x2| + |y1 - y2|.
Return the lowest total cost to connect all the points. The points are connected when every point can reach every other point along a chain of connections. Two points do not need a direct connection.
Example 1
Input: points = [[1, 1], [4, 2], [4, 6], [8, 3], [0, 5]]
18Explanation: One cheapest choice connects [1,1] with [4,2] for 4, [4,2] with [4,6] for 4, [1,1] with
[0,5] for 5, and [4,2] with [8,3] for 5. The total is 18.
Example 2
Input: points = [[3, -2]]
0Explanation: A single point needs no connection.
Example 3
Input: points = [[-1000000000, -1000000000],
[1000000000, 1000000000],
[1000000000, -1000000000]]
4000000000Explanation: The corner [1000000000,-1000000000] is 2 × 109 from each of the other two points. Two such
connections cost 4 × 109, and the direct connection between the other two would cost that
much on its own.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ points.length ≤ 2000points[i].length = 2-109 ≤ x, y ≤ 109- Two points can be at the same place.
Clarifying questions
What you would ask an interviewer before writing any code.