375. Kth Smallest Gap
A chess club records the ratings of its members. For every pair of different members, the gap of that pair is the absolute difference between their ratings. With n members there are n * (n - 1) / 2 pairs, and several pairs can have the same gap.
Given the array nums of ratings and an integer k, list the gaps of all pairs in increasing order (keeping repeats) and return the k-th one. Building all the pairs is far too big for fifty thousand members, so find a way to count the pairs below a given gap without listing them.
Example 1
- Input:
- nums = [1,3,6], k = 2
- Output:
- 3
- Explanation:
The gaps are 2 (1 and 3), 3 (3 and 6) and 5 (1 and 6), so the 2nd smallest is 3.
Example 2
- Input:
- nums = [4,4,4], k = 3
- Output:
- 0
- Explanation:
All three pairs have gap 0.
Constraints
2 ≤ nums.length ≤ 5 * 104
0 ≤ nums[i] ≤ 106
1 ≤ k ≤ nums.length * (nums.length - 1) / 2
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,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n + n log D), where D is the largest rating
- Space
- O(1)