784. Wire All Points
A farm has n soil sensors placed at the integer coordinates listed in points, where points[i] = [x, y]. Cables run only along the grid lines, so connecting sensors i and j directly needs |x_i - x_j| + |y_i - y_j| metres of cable. Several sensors may share the same coordinates.
Every sensor must end up linked, directly or through other sensors, to the control hut at sensor 0. Return the minimum total length of cable required to link all the sensors together. If there is only one sensor the answer is 0.
Example 1
- Input:
- points = [[1,4],[6,4],[2,9],[8,1]]
- Output:
- 16
- Explanation:
The cables (1,4)-(6,4) of length 5, (6,4)-(8,1) of length 5 and (1,4)-(2,9) of length 6 join all four sensors for 16, the cheapest possible.
Example 2
- Input:
- points = [[1,1],[1,1],[1,1]]
- Output:
- 0
- Explanation:
All three sensors sit at the same spot, so every cable has length 0 and the total is 0.
Example 3
- Input:
- points = [[-4,3]]
- Output:
- 0
- Explanation:
A single sensor needs no cable, so the answer is 0.
Constraints
- 1 ≤ points.length ≤ 1000
- points[i].length == 2
- -105 ≤ x, y ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)