214. Closest Neighbours
A city planner has the positions of several lampposts along a straight road, given as distinct integers in nums. The planner wants to find the lampposts that stand closest to one another.
Find the smallest absolute difference between any two positions. Then return every pair [a, b] of positions with a < b whose difference b - a equals that smallest difference. The pairs must be listed in ascending order, which means the pair with the smaller a comes first.
For example, with positions [10, 4, 7] the smallest difference is 3 and the answer is [[4, 7], [7, 10]].
Example 1
- Input:
- nums = [91,17,45,60,33]
- Output:
- [[33,45]]
- Explanation:
Sorted: 17, 33, 45, 60, 91. The differences between neighbours are 16, 12, 15 and 31, so the minimum 12 gives only the pair [33, 45].
Example 2
- Input:
- nums = [10,2,6,14,18]
- Output:
- [[2,6],[6,10],[10,14],[14,18]]
- Explanation:
Sorted: 2, 6, 10, 14, 18. Every neighbouring difference is 4, so all four neighbouring pairs are returned.
Example 3
- Input:
- nums = [-8,5]
- Output:
- [[-8,5]]
- Explanation:
With only two positions there is a single pair.
Constraints
2 ≤ nums.length ≤ 105
-106 ≤ nums[i] ≤ 106
All values in nums are distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)