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.
- n == nums.length
- 2 <= n <= 10⁴
- 0 <= nums[i] <= 10⁶
- 1 <= k <= n * (n - 1) / 2
Intuition
Find k th smallest pair distance returns the k-th smallest absolute difference among all pairs. There are n(n−1)/2 pairs, so generating and sorting them is O(n² log n) and far too slow at the given constraints.
The key realisation is that the answer is a distance value, and distances live in a bounded, ordered range — from 0 up to max − min. That range can be searched directly:
- Binary search the distance itself, asking how many pairs have distance at most mid, rather than enumerating pairs at all.
That count is monotonic in mid: a larger distance never yields fewer pairs. So the predicate "at least k pairs within this distance" is false then true, which is exactly what binary search needs.
Counting pairs within a distance requires the array sorted, which is what makes the counting linear. With a sliding window, for each right index advance the left index while nums[right] − nums[left] > mid. Every element between them forms a valid pair with right, contributing right − left pairs.
That inner count is O(n) total, not O(n²), because the left pointer only moves forward across the whole pass.
The search converges on the smallest distance whose pair count reaches k, which is precisely the k-th smallest distance.
Sorting is not an optimisation here but a prerequisite — the sliding-window count is meaningless on unsorted input. Koko Eating Bananas and Capacity to Ship Packages share this binary-search-on-the-answer structure with a different counting step.
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
Before reading on: price up what sorting first costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n log n + n log W) time and O(1) space.
Reject enumerating pairs
There are n(n-1)/2 pairs, so sorting them is O(n² log n) — far too slow. The answer is a distance value, and distances form a small ordered range.
Binary search the distance
Search candidate distances from 0 to max - min, asking how many pairs fall within each. The pair count is monotonic in the distance, which is what binary search requires.
Sort the array first
Sorting is a prerequisite, not an optimisation — the sliding-window count below is meaningless on unsorted input.
Count pairs with a sliding window
For each right index, advance left while nums[right] - nums[left] > mid. Every element between them pairs validly with right, contributing right - left pairs.
Note the linear counting cost
The left pointer only moves forward across the entire pass, so counting is O(n) per check rather than O(n²) — this is what makes the whole approach viable.
Converge on the smallest qualifying distance
When the count reaches k, search lower; otherwise search higher. The loop settles on the smallest distance with at least k pairs — the k-th smallest.
Cost of the approach
Sorting is O(n log n), and each of the O(log(max − min)) search steps costs O(n), giving O(n log n + n log(max − min)) time and O(1) extra space.
Solution & live demo
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.