719. Find K-th Smallest Pair Distance

Description

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 kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

 

Example 1:

Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Example 2:

Input: nums = [1,1,1], k = 2
Output: 0

Example 3:

Input: nums = [1,6,1], k = 3
Output: 5

 

Constraints:

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

 

Solutions

Solution: Binary Search + Two Pointers

• Time complexity: O(nlog(max(nums)-min(nums)))
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const smallestDistancePair = function (nums, k) {
  nums.sort((a, b) => a - b);

  const n = nums.length;
  let left = 0;
  let right = nums[n - 1] - nums[0];

  const getKth = distance => {
    let result = 0;
    let left = 0;
    let right = 1;

    while (right < n) {
      const num = nums[right];

      while (left < right && num - nums[left] > distance) {
        left += 1;
      }
      result += right - left;
      right += 1;
    }
    return result;
  };

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const kth = getKth(mid);

    kth >= k ? (right = mid) : (left = mid + 1);
  }
  return left;
};