DSA problem
Find K-th Smallest Pair Distance
The distance of a pair of integers a and b is defined as the absolute difference between a and b. Given an integer array nums and an integer k, return the k-th smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
A direct approach generates all O(n^2) pair distances, sorts them, and returns the k-th. That costs O(n^2 log n) time and O(n^2) memory, infeasible for n up to 10^4 (about 5 × 10^7 pairs). The trick is to binary-search the answer distance.
Sort nums first. Then define countPairs(d) = number of pairs whose distance is at most d. This count is non-decreasing in d, so binary searching for the smallest d with countPairs(d) >= k gives the k-th smallest distance.
The counting predicate uses two pointers and runs in O(n). For a fixed left index i, find the largest index j such that nums[j] - nums[i] <= d; the count contributed by i is j - i. Because the array is sorted and d is fixed, advancing i only moves j forward, so the total work for the predicate across all i is O(n).
The search range for d is [0, max - min]. Use the lower-bound shape while (lo < hi), narrow hi = mid on countPairs(mid) >= k. Total time O(n log n) for the sort plus O(n log(max - min)) for the search, dominated by the latter. Space O(1) outside the sort.
Examples
nums = [1,3,1], k = 10nums = [1,1,1], k = 20nums = [1,6,1], k = 35Constraints
- n == nums.length
- 2 <= n <= 10^4
- 0 <= nums[i] <= 10^6
- 1 <= k <= n * (n - 1) / 2
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.