Min Cost to Connect All Points
MediumP3Coding
You are given points, where points[i] = [x, y] is a point on a plane. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all the points so that there is exactly one simple path between every pair of points.
Example 1
- Input
- points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
- Output
- 20
Example 2
- Input
- points = [[3,12],[-2,5],[-4,1]]
- Output
- 18
- Why
- Connect (-4,1)-(-2,5) for 6 and (-2,5)-(3,12) for 12.
Constraints
- 1 <= points.length <= 1000
- -10^6 <= x, y <= 10^6
- All points are distinct.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.