Given a list of integers nums and an integer k, consider the distance |nums[i] - nums[j]| of every
pair i < j. Return the k-th smallest of these distances (duplicates count separately).
Examples
Input: nums = [1, 3, 1], k = 1
Output: 0
Explanation: the distances are 2, 0, 2.
Input: nums = [1, 1, 1], k = 2
Output: 0
Input: nums = [1, 6, 1], k = 3
Output: 5
Constraints
2 <= len(nums) <= 5 * 10**4,0 <= nums[i] <= 10**61 <= k <= len(nums) * (len(nums) - 1) / 2- Required time:
O(n log n + n log(max - min)). There can be over a billion pairs.
Goals
- Count pairs with distance <= d in linear time after sorting
- Binary search the distance instead of enumerating pairs