Find K-th Smallest Pair Distance
Given an integer array nums and an integer k, return the k-th smallest distance among all pairs (nums[i], nums[j]) where i < j.
Intuition
There are O(n²) pairs, so computing all distances and sorting them is too slow for large arrays. The key insight is to binary search on the answer itself — the distance value — rather than on the array. For a candidate distance d, you can efficiently count how many pairs have distance <= d using a two-pointer sweep on the sorted array. If the count is >= k, the k-th smallest distance is at most d; otherwise it is larger. Sorting the array first makes the two-pointer counting work in O(n).
When a problem asks for the k-th smallest or k-th largest value in a space too large to enumerate (like all O(n²) pairs), binary search on the answer is the go-to technique. The requirement is a function that counts 'how many values are <= candidate' in less than O(n²). Sorting plus two pointers gives that O(n) counting function here. The same pattern appears in k-th smallest element in a sorted matrix.
Approach
Sort the array to enable efficient pair counting
Sorting does not change the set of pair distances (order within a pair does not matter). After sorting, for a fixed right endpoint, all left endpoints with nums[right] - nums[left] <= d form a contiguous prefix — which is what lets a two-pointer sweep count pairs in O(n).
Binary search on the distance value, not on array indices
The smallest possible distance is 0 (two equal elements), and the largest is nums[-1] - nums[0] (the two extremes). Binary search this range. For each candidate mid, count how many pairs have distance <= mid. If the count is >= k, the answer could be mid or smaller — set right = mid. Otherwise, the answer is larger — set left = mid + 1.
Count pairs with distance `<= mid` using a sliding window
For each right index j, advance a left pointer i until nums[j] - nums[i] <= mid. All indices from i to j-1 pair with j and have distance <= mid, contributing j - i pairs. This is O(n) per count. Combined with O(log(max_distance)) binary search steps, the total is O(n log(max_distance) + n log n) for the sort.
Solution
Common pitfalls
Counting pairs with distance strictly less than mid instead of <= mid
while nums[j] - nums[i] >= mid:
i += 1while nums[j] - nums[i] > mid:
i += 1Using >= excludes pairs whose distance equals mid, undercounting. The binary search needs the count of pairs with distance <= mid to correctly bisect.
Forgetting to sort the array before the two-pointer count
left, right = 0, max(nums) - min(nums) while left < right:
nums.sort() left, right = 0, nums[-1] - nums[0] while left < right:
The two-pointer counting assumes sorted order — nums[j] - nums[i] is nonnegative and increasing as i decreases. Without sorting, the sweep gives wrong counts.
Using right = mid - 1 instead of right = mid in the binary search
if count >= k:
right = mid - 1if count >= k:
right = midThe candidate mid might be the answer itself. Setting right = mid - 1 skips it. The search converges when left == right, which is the answer. Using mid - 1 can jump past the correct distance value.
Edge cases
[1,1,1]Every pair has distance 0. The binary search converges to 0 immediately regardless of k.
k = 1 — the smallest pair distanceAfter sorting, the answer is the minimum gap between consecutive elements. The binary search finds it, though a linear scan of gaps would also work for this specific case.
Only one pair exists. The answer is abs(nums[0] - nums[1]) for any k = 1.