Description
Given an array of points on a 2D plane, return the minimum cost to connect all points. Cost is Manhattan distance.
Examples
Input:
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]Output:
20Explanation:
Connect with min total distance.
Input:
points = [[3,12],[-2,5],[-4,1]]Output:
18Explanation:
Works with negative numbers.
Input:
points = [[1,1],[1,1],[2,2]]Output:
2Explanation:
Two points are at the same location [1,1], so connecting them costs 0. The third point [2,2] needs to be connected to either duplicate point with Manhattan distance |2-1| + |2-1| = 2. Total minimum cost is 0 + 2 = 2.
Constraints
- •
1 ≤ points.length ≤ 1000