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
- code
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
l, r = 0, nums[-1] - nums[0]
while l < r:
mid = l + (r - l) // 2
start = ct = 0
# how many pairs distance <= mid
for i in range(len(nums)):
while nums[i] - nums[start] > mid:
start += 1
ct += i - start # for i, [start, ..., i-1 ,i], every pair dis (start, i).. (i-1, i) <= mid
if ct < k: # need to increase counts
l = mid + 1
else:
r = mid
return r # or l