719

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        // Sort the array.
        sort(nums.begin(), nums.end());

        int n = nums.size();
        int l=0, r=nums[n-1]-nums[0];

        // Leftmost binary search.
        while(l<r){
            int count = 0;
            int mid = (l+r)/2;

            // Count pairs with difference less-equal to mid.
            for(int left=0, right=0; right<n; right++){
                while(nums[right]-nums[left] > mid)
                    left++;
                count += right-left;
            }
            if(count < k)
                l = mid+1;
            else
                r = mid;
        }
        return l;
    }
};