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.length2 <= n <= 1040 <= nums[i] <= 1061 <= 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
}
Input
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
Input
nums = [1,3,1], k = 1
#3 Code Example with C# Programming
Code -
C# Programming
start coding...