Description
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
Solution
Python3
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
N = len(nums)
nums.sort()
# find the number of pairs where nums[j] - nums[i] <= mid
def good(mid):
count = 0
i = 0
for j in range(N):
while nums[j] - nums[i] > mid:
i += 1
count += (j - i)
return count >= k
return bisect_left(range(10 ** 7), True, key = good)