K-th Smallest Pair Gap
The *gap* of a pair of positions i < j is |nums[i] - nums[j]|. Among all n * (n - 1) / 2 pairs, return the k-th smallest gap (1-indexed).
Example 1
Input: nums = [4, 9, 2, 7], k = 2 Output: 2 Explanation: Gaps sorted: 2, 2, 3, 5, 5, 7.
Example 2
Input: nums = [1, 6, 1], k = 3 Output: 5
Constraints
- 2 <= nums.length <= 2 * 10^4
- 0 <= nums[i] <= 10^6
- 1 <= k <= n * (n - 1) / 2
Hint 1
Sort the values, then binary search on the gap itself.
Hint 2
For a candidate gap d, a sliding window counts the pairs with gap <= d in O(n).
Discussion 0
Join free to post in the discussion.
Good practice for: Data Scientist, Data Engineer, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Game Developer
Run checks your code on 2 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.