Find K-th Smallest Pair Distance LeetCode solution in Java

1
class Solution {
2
  public int smallestDistancePair(int[] nums, int k) {
3
    Arrays.sort(nums);
4
    int low = 0, high = nums[nums.length - 1] - nums[0];
5

6
    while (low <= high) {
7
      int mid = low + (high - low) / 2;
8
      if (noOfDistancesLessThan(mid, nums) >= k) high = mid - 1;
9
      else low = mid + 1;
10
    }
11
    return low;
12
  }
13

14
  private int noOfDistancesLessThan(int dist, int[] nums) {
15
    int count = 0, i = 0, j = 0;
16
    while (i < nums.length) {
17
      while (j < nums.length && nums[j] - nums[i] <= dist) { // sliding window
18
        j++;
19
      }
20
      count += j - i - 1;
21
      i++;
22
    }
23
    return count;
24
  }
25
}