The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 &lt;= i &lt; j &lt; nums.length.

&nbsp;
Example 1:

Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -&gt; 2
(1,1) -&gt; 0
(3,1) -&gt; 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.


Example 2:

Input: nums = [1,1,1], k = 2
Output: 0


Example 3:

Input: nums = [1,6,1], k = 3
Output: 5


&nbsp;
Constraints:


	n == nums.length
	2 &lt;= n &lt;= 104
	0 &lt;= nums[i] &lt;= 106
	1 &lt;= k &lt;= n * (n - 1) / 2


from heapq import heappush, heappop, heapify
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        # pairs = list(combinations(nums, 2))
        
        maxHeap = []
        heapify(maxHeap)
        
        for idx, val1 in enumerate(nums):
            for val2 in nums[idx + 1:]:
                pair = [val1, val2]
                heappush(maxHeap, [-1*abs(pair[0] - pair[1]), pair])
                if len(maxHeap) > k:
                    heappop(maxHeap)
        
        return -1*maxHeap[0][0]
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 0, high = nums[nums.length-1] - nums[0];
        
        while(low<=high){
            int mid = low + (high-low)/2;
            if(noOfDistancesLessThan(mid,nums) >= k) high = mid - 1;
            else low = mid + 1;
        }
        return low;
    }
    private int noOfDistancesLessThan(int dist,int[] nums){
        int count = 0,i = 0, j = 0;
        while(i<nums.length){
            while(j<nums.length && nums[j]-nums[i]<=dist){  // sliding window
                j++;
            }
            count += j-i-1;
            i++;
        }
        return count;
    }
}
class Solution {
public:
    int count(vector<int> &temp,int mid){
        int i=0,j=0,n=temp.size();
        int len=0;

        while(i<n){
            while(j<n && (temp[j]-temp[i])<=mid) j++;
            len+=j-i-1;
            i++;
        }
        return len;
    }
    int smallestDistancePair(vector<int>& nums, int k) {
        int s=0,e=1e6;
        int ans=0;
        vector<int> temp=nums;
        sort(temp.begin(),temp.end());
        while(s<=e){
            int mid=s+(e-s)/2;

            if(count(temp,mid)>=k){
                ans=mid;
                e=mid-1;
            }else {
                s=mid+1;
            }
        }
        return ans;
    }
};
var smallestDistancePair = function(nums, k) {    
    nums.sort((a,b) => a - b);   
    let left = 0, right = nums[nums.length-1] - nums[0], mid = null, total = 0;    
    
    while (left < right) {
        mid = left + Math.floor((right - left) / 2);
    
        total = 0;
        for (var i = 0, j = 1; i < nums.length - 1 && total <= k; i++) {
            for ( ; j < nums.length && nums[j] - nums[i] <= mid; j++) {}
			total += j - i - 1; 
        }
        
        if (total >= k) {right = mid;}  
		else {left = mid+1;}
    }    
	
    return left;
};
Find K-th Smallest Pair Distance