Algorithm

Problem Name: 719. Find K-th Smallest Pair Distance

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 <= i < j < nums.length`.

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.
```

Example 2:

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

Example 3:

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

Constraints:

• `n == nums.length`
• `2 <= n <= 104`
• `0 <= nums[i] <= 106`
• `1 <= k <= n * (n - 1) / 2`

Code Examples

#1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function smallestDistancePair(nums, k) {
nums.sort((a, b) => a - b)
let l = 0, n = nums.length, r = nums[n - 1] - nums[0]

let res = 0
while(l < r) {
let cnt = 0, mid = l + ((r - l) >> 1)
for(let i = 0, j = 0; i  <  n; i++) {
while(j < n && nums[j] <= nums[i] + mid) j++
cnt += j - 1 - i
}
if(cnt < k> l = mid + 1
else r = mid
}

return l
}
``````
Copy The Code &

Input

cmd
nums = [1,3,1], k = 1

#2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def countPairsLTE(self, array, value):
return sum(bisect.bisect_right(array, array[i] + value, lo = i) - i - 1 for i in range(len(array)))

def smallestDistancePair(self, nums, k):
nums.sort()
low, high = min([nums[i + 1] - nums[i] for i in range(len(nums) - 1)]), nums[-1] - nums[0]
while low < high:
mid = (low + high) // 2
if self.countPairsLTE(nums, mid) < k:
low = mid + 1
else:
high = mid
return low
``````
Copy The Code &

Input

cmd
nums = [1,3,1], k = 1

#3 Code Example with C# Programming

```Code - C# Programming```

``start coding...``
Copy The Code &