Find K-th Smallest Pair Distance
Hard · Binary Search · Array · Two Pointers · Binary Search · Sorting
Problem
The distance of a pair of integers a and b is |a - b|. Given an integer array nums and an integer k, consider every pair (nums[i], nums[j]) with 0 <= i < j < len(nums).
Return the k-th smallest distance among all these pairs, counting pairs with equal distances separately.
Examples
Input: nums = [1,6,3], k = 2 Output: 3
The pair distances are 2, 3 and 5; the second smallest is 3.
Input: nums = [4,4,4,9], k = 4 Output: 5
Three pairs have distance 0 and three have distance 5, so the fourth smallest is 5.
Input: nums = [2,8], k = 1 Output: 6
There is only one pair, with distance 6.
Constraints
- 2 <= len(nums) <= 10^4
- 0 <= nums[i] <= 10^6
- 1 <= k <= len(nums) · (len(nums) - 1) / 2
Approaches
- Baseline: list every distance and sort — time O(n² log n), space O(n²)
Follow-up
The counting step stands on its own (the first use case), and the same "search the threshold, count greedily" idea answers questions like "what is the smallest possible largest gap if you must form p disjoint pairs?" (the second). How would you find the k-th smallest sum of pairs instead?
Related problems
Start free on Cariara · Coding problems · System design studio
