719. Find K-th Smallest Pair Distance

Question:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

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.

Note:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

Solution:

  • Method 1: Bucket sort 
      class Solution {
      public int smallestDistancePair(int[] nums, int k) {
          int len = nums.length;
          int size = len * (len - 1) / 2;
          int[] arr = new int[1000000];
          for(int i = 0; i < len; i++){
              for(int j = i + 1; j < len; j++){
                  arr[Math.abs(nums[i] - nums[j])]++;
              }
          }
          int cur = 0;
          while(k > 0){
              k -= arr[cur++];
          }
          return cur - 1;
      }
  }
  • Method 2: Binary Search + dp 
      class Solution {
      public int smallestDistancePair(int[] nums, int k) {
          Arrays.sort(nums);
          int len = nums.length;
          int left = 0, right = nums[nums.length - 1];
          while(left <= right){
              int mid = left + (right - left) / 2;
              int j = 0;
              int count = 0;
              for(int i = 0; i < len; i++){
                  while(j < len && nums[j] - nums[i] <= mid) ++j;
                  count += j - i - 1;
              }
              if(count >= k) right = mid - 1;
              else left = mid + 1;
          }
          return left;
      }
  }