content: class Solution {
      public int smallestDistancePair(int[] nums, int k) {
          Arrays.sort(nums);
          int WIDTH = 2 * nums[nums.length - 1];
  
          //multiplicity[i] = number of nums[j] == nums[i] (j < i)
          int[] multiplicity = new int[nums.length];
          for (int i = 1; i < nums.length; ++i) {
              if (nums[i] == nums[i-1]) {
                  multiplicity[i] = 1 + multiplicity[i - 1];
              }
          }
  
          //prefix[v] = number of values <= v
          int[] prefix = new int[WIDTH];
          int left = 0;
          for (int i = 0; i < WIDTH; ++i) {
              while (left < nums.length && nums[left] == i) left++;
              prefix[i] = left;
          }
  
          int lo = 0;
          int hi = nums[nums.length - 1] - nums[0];
          while (lo < hi) {
              int mi = (lo + hi) / 2;
              int count = 0;
              for (int i = 0; i < nums.length; ++i) {
                  count += prefix[nums[i] + mi] - prefix[nums[i]] + multiplicity[i];
              }
              //count = number of pairs with distance <= mi
              if (count >= k) hi = mi;
              else lo = mi + 1;
          }
          return lo;
      }
  }