LeetCode [719] Find K-th Smallest Pair Distance

719. Find K-th Smallest Pair Distance

Hard

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.

class Solution {
    int[] sortedNums;
    int n;
    public int smallestDistancePair(int[] nums, int k) {
        this.sortedNums = nums;
        Arrays.sort(sortedNums);
        n = nums.length;
        int l = 0, r = sortedNums[n-1]-sortedNums[0];
        
        //upon exiting, l is the k-th smallest diff
        while(l<r){
            int m = l+(r-l)/2;
            if(cnt(m)<k) l = m+1;
            else r = m;
        }
        
        return l;
    }
    
    //return the number of pairs whose diff is <= x
    int cnt(int x){
        int c = 0;
        for(int i=0, j=0; i<n-1; ++i){
            while(j<n && sortedNums[j]-sortedNums[i]<=x) j++;
            c += j-i-1;
        }
        return c;
    }
}