The k-th smallest distance between two values
The distance of a pair of values a, b is |a − b|. Given an array
nums, return the k-th smallest distance among all pairs nums[i],
nums[j] with i < j, counting repeats.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 3, 1], k = 1 | 0 | Distances: 2, 0, 2. The smallest is 0. |
nums = [1, 1, 1], k = 2 | 0 | |
nums = [1, 6, 1], k = 3 | 5 | Distances: 5, 0, 5. |
Constraints
- 2 ≤ n ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁶
- 1 ≤ k ≤ n(n − 1)/2
Hints
Hint 1
Listing all distances is up to 5 × 10⁷ values. Instead, for a distance d, can you count the pairs at distance ≤ d quickly?
Hint 2
Sort the array. For each right end hi, the values within d of nums[hi] on its left form a window [lo, hi − 1], and lo only moves right as hi does.
Hint 3
That count is non-decreasing in d. Search d in [0, max − min] for the first d whose count is at least k.
Where people lose marks
- Counting pairs with a nested loop inside the search: O(n² log W), too slow at n = 10⁴.
- Moving lo back to 0 for each hi, which also makes the count quadratic.
- Counting each pair twice (as i, j and j, i), or counting a value paired with itself.
Dry run on [13,1,8,4,10,6],7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 12lo0hi12
Sorted: 1, 4, 6, 8, 10, 13. 15 pairs; distances run from 0 to 12. Find the smallest d with at least 7 pairs within d.
-
Step 2 / 12lo0mid6hi12
10 pairs are within 6, at least 7. 6 works, so the answer is 6 or smaller: hi = 6.
-
Step 3 / 12lo0mid3hi6
5 pairs are within 3, fewer than 7. 3 fails, so does everything below it: lo = 4.
-
Step 4 / 12lo4mid5hi6
9 pairs are within 5, at least 7. 5 works, so the answer is 5 or smaller: hi = 5.
-
Step 5 / 12lo4mid4hi5
7 pairs are within 4, at least 7. 4 works, so the answer is 4 or smaller: hi = 4.
-
Step 6 / 12answer4
lo = hi = 4: 7 pairs within 4, 5 within 3. The 7-th smallest distance is 4.
-
Step 7 / 12d4pairs so far0
The count at d = 4, right end 1: values from 1 are within 4, so 0 new pairs. lo never moves left.
-
Step 8 / 12d4pairs so far1
The count at d = 4, right end 4: values from 1 are within 4, so 1 new pair. lo never moves left.
-
Step 9 / 12d4pairs so far2
The count at d = 4, right end 6: values from 4 are within 4, so 1 new pair. lo never moves left.
-
Step 10 / 12d4pairs so far4
The count at d = 4, right end 8: values from 4 are within 4, so 2 new pairs. lo never moves left.
-
Step 11 / 12d4pairs so far6
The count at d = 4, right end 10: values from 6 are within 4, so 2 new pairs. lo never moves left.
-
Step 12 / 12d4pairs so far7
The count at d = 4, right end 13: values from 10 are within 4, so 1 new pair. lo never moves left. Total 7 ≥ 7.
How to think about it
Three ideas from earlier modules combine here.
- Search the value, not a position. The answer is a distance between 0 and
max − min, and the k-th smallest distance is the smallestdwith at leastkpairs at distance≤ d. - Count with a window. After sorting, the pairs ending at index
hiwith distance≤ dare those starting in[lo, hi − 1], wherelois the first index withnums[hi] − nums[lo] ≤ d. Ashimoves right,lonever moves left, so one pass counts every pair in O(n). - The first passing value is a real distance. The count only changes at values that are distances of some pair, so the search lands on one.
Sorting costs O(n log n) and the search O(n log W), where W is the range of values.
A heap of candidate pairs also works, in O((n + k) log n), but k can be 5 × 10⁷. The value search does not care how large k is.
Complexity. Time O(n log n + n log W) · Space O(1) beyond the sort
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def kth_distance(nums, k):
s = sorted(nums)
def pairs_at_most(d): # sliding window: lo only moves right
count = lo = 0
for hi in range(len(s)):
while s[hi] - s[lo] > d:
lo += 1
count += hi - lo # pairs (lo..hi-1, hi)
return count
lo, hi = 0, s[-1] - s[0]
while lo < hi:
mid = (lo + hi) // 2
if pairs_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo#include <vector>
#include <algorithm>
int solve(std::vector<int> s, long long k) {
std::sort(s.begin(), s.end());
auto pairsAtMost = [&](int d) { // sliding window: lo only moves right
long long count = 0;
int lo = 0;
for (int hi = 0; hi < (int)s.size(); ++hi) {
while (s[hi] - s[lo] > d) ++lo;
count += hi - lo;
}
return count;
};
int lo = 0, hi = s.back() - s.front();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (pairsAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}import java.util.Arrays;
class Solution {
public int kthDistance(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;
long count = 0;
for (int r = 0, l = 0; r < s.length; r++) { // sliding window
while (s[r] - s[l] > mid) l++;
count += r - l;
}
if (count >= k) hi = mid; else lo = mid + 1;
}
return lo;
}
}function kthDistance(nums, k) {
const s = nums.slice().sort((a, b) => a - b);
const pairsAtMost = d => { // sliding window: lo only moves right
let count = 0, lo = 0;
for (let hi = 0; hi < s.length; hi++) {
while (s[hi] - s[lo] > d) lo++;
count += hi - lo;
}
return count;
};
let lo = 0, hi = s[s.length - 1] - s[0];
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (pairsAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve(nums: &[i64], k: i64) -> i64 {
let mut s = nums.to_vec();
s.sort();
let pairs_at_most = |d: i64| -> i64 { // sliding window: lo only moves right
let (mut count, mut lo) = (0i64, 0usize);
for hi in 0..s.len() {
while s[hi] - s[lo] > d {
lo += 1;
}
count += (hi - lo) as i64;
}
count
};
let (mut lo, mut hi) = (0i64, s[s.len() - 1] - s[0]);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if pairs_at_most(mid) >= k { hi = mid } else { lo = mid + 1 }
}
lo
}import Data.Array
import Data.List (sort)
solve :: [Int] -> Int -> Int
solve nums k = go 0 (s ! (n - 1) - s ! 0)
where
n = length nums
s = listArray (0, n - 1) (sort nums)
-- sliding window: for each right end, lo only moves right
pairsAtMost d = walk 0 0 0
where
walk hi lo acc
| hi == n = acc
| s ! hi - s ! lo > d = walk hi (lo + 1) acc
| otherwise = walk (hi + 1) lo (acc + hi - lo)
go lo hi
| lo >= hi = lo
| pairsAtMost mid >= k = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- The k-th smallest sum of pairs from two sorted arrays: the same search with a two-pointer count.
- The k-th largest distance: the (total − k + 1)-th smallest.
Next problems
The k-th smallest value in a sorted matrix
Search over values, not positions: count the cells ≤ x with a staircase walk in O(n), and find the smallest x whose count reaches k.
Open the problem → Hard25 minThe k-th smallest entry of a multiplication table
Row i of the table holds i, 2i, …, ni, so it has min(⌊x / i⌋, n) entries ≤ x. Count in O(m) and search for the first value whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The k-th smallest value in a sorted matrix
Search over values, not positions: count the cells ≤ x with a staircase walk in O(n), and find the smallest x whose count reaches k.
Open the problem → Hard25 minThe k-th smallest entry of a multiplication table
Row i of the table holds i, 2i, …, ni, so it has min(⌊x / i⌋, n) entries ≤ x. Count in O(m) and search for the first value whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.