477. Find K-th Smallest Pair Distance
You are given an integer array nums and an integer k.
The distance of a pair of indices (i, j) with i < j is |nums[i] - nums[j]|. An array of length n has n·(n−1)/2 such pairs, and equal distances are counted as many times as they occur.
Return the k-th smallest pair distance (1-indexed). For example, if the multiset of all pair distances is {0, 2, 2}, then the 1st smallest is 0 and both the 2nd and 3rd are 2.
Example 1:
Input: nums = [1, 3, 1], k = 1
Output: 0
Explanation: The three pairs have distances |1−3| = 2, |1−1| = 0, and |3−1| = 2. Sorted: 0, 2, 2 — the 1st smallest is 0.
Example 2:
Input: nums = [1, 6, 1], k = 3
Output: 5
Explanation: Distances are 5, 0, 5; sorted: 0, 5, 5. The 3rd smallest is 5 (duplicates count separately).
Constraints:
- 2 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁶
- 1 ≤ k ≤ nums.length * (nums.length - 1) / 2
Hints:
Materializing all n·(n−1)/2 distances works for small n, but at n = 10^4 that is ~5·10^7 values — think about finding the answer without listing them.
Flip the question: for a candidate distance d, how many pairs have distance <= d? That count is monotone in d, which is the green light for binary searching on the answer itself.
After sorting, count(d) is a single sliding-window pass: for each right endpoint, advance left while nums[right] − nums[left] > d; the window then contributes right − left pairs. The answer is the smallest d with count(d) >= k.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 1], k = 1
Expected output: 0