Find K-th Smallest Pair Distance

hard binary search two pointers sorting

Problem

Given an integer array nums, return the k-th smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length. The distance of a pair is defined as the absolute difference between the two numbers.

Inputnums=[1,3,1], k=1

Output0

Pair distances are [0,2,2]; the 1st smallest is 0.

input

def smallestDistancePair(nums, k):
    nums.sort()
    lo, hi = 0, nums[-1] - nums[0]
    while lo < hi:
        mid = (lo + hi) // 2
        count = left = 0
        for right, x in enumerate(nums):
            while x - nums[left] > mid:
                left += 1
            count += right - left
        if count >= k: hi = mid
        else: lo = mid + 1
    return lo

function smallestDistancePair(nums, k) {
  nums.sort((a, b) => a - b);
  let lo = 0, hi = nums[nums.length - 1] - nums[0];
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    let count = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
      while (nums[right] - nums[left] > mid) left++;
      count += right - left;
    }
    if (count >= k) hi = mid; else lo = mid + 1;
  }
  return lo;
}

class Solution {
  public int smallestDistancePair(int[] nums, int k) {
    Arrays.sort(nums);
    int lo = 0, hi = nums[nums.length - 1] - nums[0];
    while (lo < hi) {
      int mid = (lo + hi) / 2, count = 0, left = 0;
      for (int right = 0; right < nums.length; right++) {
        while (nums[right] - nums[left] > mid) left++;
        count += right - left;
      }
      if (count >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
  }
}

class Solution {
public:
  int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.back() - nums.front();
    while (lo < hi) {
      int mid = (lo + hi) / 2, count = 0, left = 0;
      for (int right = 0; right < (int)nums.size(); right++) {
        while (nums[right] - nums[left] > mid) left++;
        count += right - left;
      }
      if (count >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
  }
};

Explanation

There can be a huge number of pairs, so listing every distance is too slow. Instead we binary-search on the answer: we guess a distance and ask "how many pairs have distance at most this?" — then home in on the right value.

First we sort the numbers. The smallest possible distance is 0 and the largest is nums[-1] - nums[0], so the answer lives in that range. For a guessed distance mid, we count pairs with distance <= mid using a sliding window: for each right, we advance left until nums[right] - nums[left] <= mid, and then every index between left and right forms a valid pair, adding right - left.

If that count is >= k, the k-th distance is mid or smaller, so we shrink hi = mid. Otherwise we need a bigger distance, so lo = mid + 1. The loop converges on the smallest distance whose count reaches k.

Example: nums = [1,3,1] sorts to [1,1,3], k = 1. Guessing distance 0 already counts one pair (the two 1s), which is >= 1, so the answer is 0.

Sorting is O(n log n), and each binary-search step counts in O(n) over a range of width W, giving O(n log W) for the search.

Time: O(n log n + n log W) Space: O(1)