0% completed
Problem Statement
You are given an array points
representing integer coordinates of some points on a 2D-plane, where points[i] = [x<sub>i</sub>, y<sub>i</sub>].
The cost of connecting two points [x<sub>i</sub>, y<sub>i</sub>] and [x<sub>i</sub>, y<sub>i</sub>] is the Manhattan distance between them: |x<sub>i</sub> - x<sub>i</sub>| + |y<sub>i</sub> - y<sub>i</sub>|, where |val|
denotes the absolute value of val
.
Return the minimum cost
to connect all the points such that each point is connected directly or indirectly to every other point with exactly one simple path between any two points.
Examples
- Example 1:
- Input: points =
[[1, 1], [2, 2], [2, 4], [3, 3]]
- Expected Output:
6
- Input: points =
- Justification: The optimal connections are
[(1,1) -> (2,2)]
,[(2,2) -> (3,3)]
and[(2,2) -> (2,4)]
with distances2
,2
and2
respectively, summing up to6
.
- Example 2:
- Input: points =
[[0, 0], [1, 2], [3, 3]]
- Expected Output:
6
- Input: points =
- Justification: The optimal connections are
[(0,0) -> (1,2)]
and[(1,2) -> (3,3)]
with distances3
and3
respectively, summing up to6
.
- Example 3:
- Input: points =
[[0, 0], [2, 4], [4, 2], [6, 6]]
- Expected Output:
16
- Input: points =
- Justification: The optimal connections are
[(0,0) -> (2,4)]
,[(2,4) -> (4,2)]
and[(4,2) -> (6,6)]
with distances6
,4
and6
respectively, summing up to16
.
Constraints:
- 1 <= points.length <= 1000
- -10<sup>6</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>6</sup>
- All pairs (x<sub>i</sub>, y<sub>i</sub>) are distinct.
Try it yourself
Try solving this question here:
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible