528. Closest Two Posts
A rancher has driven fence posts into a flat field. The array points lists the position of each post as [x, y]. To plan a gate, the rancher wants to know how close the nearest pair of posts is.
Return the squared straight-line distance between the two closest posts, that is the minimum over all pairs of (x1 - x2)^2 + (y1 - y2)^2. Squared values keep everything in whole numbers. Two different posts may stand at the same position, in which case the answer is 0. The array always contains at least two posts.
Example 1
- Input:
- points = [[2,3],[12,30],[40,50],[5,1],[12,10],[3,4]]
- Output:
- 2
- Explanation:
Posts (2,3) and (3,4) are the closest pair, with squared distance 1+1 = 2.
Example 2
- Input:
- points = [[-4,-4],[9,9]]
- Output:
- 338
- Explanation:
Only one pair exists: the offsets are 13 in each direction, so 13^2 + 13^2 = 338.
Constraints
2 ≤ points.length ≤ 105
-107 ≤ x, y ≤ 107
Points may repeat; the result fits in a 64-bit integer
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log^2 n)
- Space
- O(n)