# 719 Find K-th Smallest Pair Distance

給一正整數矩陣nums和一正整數k。pair distance是任意兩element相減的差，問nums中第k小的pair distance。

Idea sort nums之後，nums中最小可能pair distance為0，最大為nums[N-1]-nums[0]。 以binary search在lo=0和hi=nums[N-1]-nums[0]的範圍中，每次把lo和hi的範圍砍半，看其中比中間值小的pair distance有幾個。若有k個，則代表找到目標。

Pseudocode

sort nums
lo = 0, hi = nums[N-1]-nums[0]

while(lo <= hi)
    mid = lo +(hi-lo)/2
    int count = 0, maxDist = 0
    for(start = 0, end = 0; end < N; end++)
        fixed end position, and move start pos to make sure pair dist smaller than mid
        count += end-start
        update maxDist

    if(count == k) kth pair distance found
    else if(count < k) search the other half
    else search current half

Code

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int lo = 0, hi = nums[n-1] - nums[0];

        while(lo <= hi){
            int mid = lo + (hi-lo)/2;
            int count = 0, maxDist = 0;
            for(int start = 0, end = 0; end < nums.length; end++){
                while(nums[end] - nums[start] > mid) start++;
                if(start < end){
                    count += end - start;
                    maxDist = Math.max(maxDist, nums[end] - nums[start]); 
                }
            }
            if(count == k)  return maxDist;
            else if(count < k) lo = mid+1;
            else    hi = mid-1;
        }
        return lo;
    }
}