Connect All Points
Advanced
points[i] = [x, y] are points on a plane. The cost to connect two points is their Manhattan distance |x1 - x2| + |y1 - y2|. Return the least total cost to connect all points so that any point can reach any other (cables can be shared).
For [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] the answer is 20.
Examples
Example 1
Input:
min_cost_connect_points([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]])
Output:
20
Example 2
Input:
min_cost_connect_points([[3, 12], [-2, 5], [-4, 1]])
Output:
18
Constraints
0 <= len(points) <= 1000-10**6 <= x, y <= 10**6
Theory
Go to TheoryKeywords
dsa-sheetgraphsspanning-trees-and-components
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.