Find K-th Smallest Pair Distance — Problem & Solution
Find K-th Smallest Pair Distance solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find K-th Smallest Pair Distance is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google and Apple interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The distance of a pair (a, b) is |a - b|.
Given nums, return the k-th smallest distance among all n · (n - 1) / 2 index pairs.
Example 1
Input: nums = [1,3,1], k = 1
Output: 0
Explanation: The three distances are 0, 2 and 2.
Example 2
Input: nums = [1,1,1], k = 2
Output: 0
Example 3
Input: nums = [1,6,1], k = 3
Output: 5
Explanation: The distances are 0, 5 and 5.
Constraints
2 <= nums.length <= 100000 <= nums[i] <= 10000001 <= k <= nums.length · (nums.length - 1) / 2
Hints for Find K-th Smallest Pair Distance
Hint 1
Materialising every distance is
O(n²)— too many to sort at the upper limit.Hint 2
Binary search the answer: for a candidate distance
d, how many pairs are at mostdapart?Hint 3
On a sorted array that count is a two-pointer sweep, and it is non-decreasing in
d.
How to solve Find K-th Smallest Pair Distance
Binary search over the distance rather than over the data. Counting pairs within a given distance is cheap on a sorted array, and the count is monotone in the distance, so the smallest distance whose count reaches k is the answer.
Approach
- Sort
nums. The candidate distances lie in[0, max - min]. countLE(d): sliderforward, advancinglwhiles[r] - s[l] > d; eachrcontributesr - lpairs.- Binary search the smallest
dwithcountLE(d) >= k.
Why it works
countLE is non-decreasing in d, so the predicate countLE(d) >= k flips exactly once — that boundary is the k-th smallest distance, because a distance is achieved by some pair precisely when the count strictly increases there. The sweep is linear: l only moves right, since a larger s[r] can only push the feasible start further along.
Complexity
- Time —
O(n log n + n log M) where M is the value range - Space —
O(n)
Pitfalls
- Binary searching on indices instead of on the distance value gets the monotonicity wrong.
cnt += r - l, notr - l + 1— a value is not paired with itself.- The count reaches about
5 · 10^7, which fitsintbut overflows a 16-bit accumulator.
Reference solution
Python
from typing import List
def smallestDistancePair(nums: List[int], k: int) -> int:
s = sorted(nums)
def count_le(d: int) -> int:
cnt = 0
l = 0
for r in range(len(s)):
while s[r] - s[l] > d:
l += 1
cnt += r - l
return cnt
lo, hi = 0, s[-1] - s[0]
while lo < hi:
mid = (lo + hi) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return loJava
public static int smallestDistancePair(int[] nums, int k) {
int[] s = nums.clone();
Arrays.sort(s);
int lo = 0, hi = s[s.length - 1] - s[0];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0, l = 0;
for (int r = 0; r < s.length; r++) {
while (s[r] - s[l] > mid) l++;
cnt += r - l;
}
if (cnt >= k) hi = mid; else lo = mid + 1;
}
return lo;
}C++
int smallestDistancePair(vector<int>& nums, int k) {
vector<int> s = nums;
sort(s.begin(), s.end());
int n = (int) s.size();
int lo = 0, hi = s[n - 1] - s[0];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0, l = 0;
for (int r = 0; r < n; r++) {
while (s[r] - s[l] > mid) l++;
cnt += r - l;
}
if (cnt >= k) hi = mid; else lo = mid + 1;
}
return lo;
}JavaScript
var smallestDistancePair = function(nums, k) {
var s = nums.slice().sort(function(a, b) { return a - b; });
var countLE = function(d) {
var cnt = 0, l = 0;
for (var r = 0; r < s.length; r++) {
while (s[r] - s[l] > d) l++;
cnt += r - l;
}
return cnt;
};
var lo = 0, hi = s[s.length - 1] - s[0];
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
if (countLE(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms