We’re preparing your current view and syncing the latest data.
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
An array points of size n where each element is an array of two integers representing the coordinates of the point.
Return an integer representing the minimum total cost to connect all points.
1 <= points.length <= 1000 -10^6 <= xi, yi <= 10^6
Example 1
Input
[[0,0],[2,2],[3,10],[5,2],[7,0]]
Output
20
Explanation
One way to connect all points with minimum cost 20 is to connect points in the following order: (0,0) -> (2,2) -> (5,2) -> (7,0) -> (3,10).
Example 2
Input
[[3,12],[-2,5],[-4,1]]
Output
18
Explanation
Connecting points (3,12) to (-2,5) and then (-2,5) to (-4,1) yields the minimum cost 18.