BS on Answer — Find K-th Smallest Pair Distance
↗ LeetCode: Find K-th Smallest Pair Distance · Hard · pattern chapter →
Given nums and integer k, return the k-th smallest absolute distance among all pairs.
Example 1 — nums=[1,3,1], k=1 → 0 (pair (1,1) has distance 0) Example 2 — nums=[1,1,1], k=2 → 0 (all pairs distance 0) Example 3 — nums=[1,6,1], k=3 → 5
Constraints — 2 ≤ n ≤ 10⁴. Brute enumerate-and-sort is O(n² log n²) ≈ 5·10⁷ · 25 = 10⁹ ops = TLE. BS-on-answer + counting is O(n log n + log(max) · n) ≈ 10⁵.
Interview timer00:00
Approach 1 — Enumerate all pairs, sort
O(n²) pairs, O(n² log n²) sort. TLE at n=10⁴.
Approach 2 — Binary search on distance + sliding window count
Insight. Sort the array. countLE(d) = number of pairs with distance ≤ d — computed via sliding window in O(n): for each right j, shrink left i while a[j] - a[i] > d; add j - i pairs.
countLE(d) is monotonic in d. Binary-search the smallest d with countLE(d) ≥ k.
int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int lo = 0, hi = nums[n - 1] - nums[0];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0, i = 0;
for (int j = 0; j < n; j++) {
while (nums[j] - nums[i] > mid) i++;
count += j - i;
}
if (count < k) lo = mid + 1;
else hi = mid;
}
return lo;
}Complexity — Time O(n log(max-min)); Space O(1) aside from sort.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Enumerate all pairs | O(n²) | O(n²) |
| BS on distance | O(n log(max-min)) | O(1) |
When to use which
- "kth-smallest of computable pair metric" → BS on answer + count-≤ function.
- All-pair distinct sums → same idea.
- Streaming → not directly applicable — need offline.