Find K-th Smallest Pair Distance

The problem. The distance of a pair of values is their absolute difference. Given an integer array nums and an integer k, return the k-th smallest distance among all pairs nums[i], nums[j] with i < j.

Example

nums = [1, 3, 1], k = 1     ->  0   (distances 2, 0, 2)
nums = [1, 1, 1], k = 2     ->  0
nums = [1, 6, 1], k = 3     ->  5
nums = [1, 3, 4, 8], k = 4  ->  4

The idea: binary search the distance, count with two pointers

There are n(n − 1)/2 pairs — too many to list for n = 10⁴. Instead, ask how many pairs are at most d apart. That count only grows with d, so the answer is the first d whose count reaches k: binary search d between 0 and max − min. Counting is fast once nums is sorted: slide a window so its values span at most d; each new right end a[right] pairs with every value in the window, which adds right − left pairs. The left end only moves forward, so a count is O(n).

1. List every distance and sort

1function smallestDistancePair(nums, k) {2  const distances = [];3  for (let i = 0; i < nums.length; i++) {4    for (let j = i + 1; j < nums.length; j++) distances.push(Math.abs(nums[i] - nums[j]));5  }6  distances.sort((a, b) => a - b);7  return distances[k - 1];8}

Time O(n² log n), space O(n²). Fifty million distances for n = 10⁴: too much memory and time.

2. Binary search on the distance

1function smallestDistancePair(nums, k) {2  const a = [...nums].sort((x, y) => x - y);3  const countWithin = (d) => {                   // how many pairs are at most d apart?4    let count = 0, left = 0;5    for (let right = 0; right < a.length; right++) {6      while (a[right] - a[left] > d) left++;     // shrink until the window spans at most d7      count += right - left;                     // a[right] pairs with every value in the window8    }9    return count;10  };11  let low = 0;12  let high = a[a.length - 1] - a[0];13  while (low < high) {14    const mid = low + Math.floor((high - low) / 2);15    if (countWithin(mid) >= k) high = mid;       // at least k pairs within mid: the answer is mid or less16    else low = mid + 1;                          // fewer than k: the answer is bigger17  }18  return low;19}

Time O(n log n + n log W), space O(n) for the sorted copy, where W is the largest value. The answer is always a real distance: the first d whose count reaches k is the k-th distance itself. Use a 64-bit count — n = 10⁴ has about 5 × 10⁷ pairs, which fits an int, but bigger inputs wouldn't.

Comparing the approaches

Edge cases to test

Variations