## # 719. Find K-th Smallest Pair Distance

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example:

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

Note:
`2 <= len(nums) <= 10000`.
`0 <= nums[i] < 1000000`.
`1 <= k <= len(nums) * (len(nums) - 1) / 2`.

### # Solution

Approach 1: find all distances in `O(N^2)`, then put those distances into buckets as in bucket sort. Time: `NlogN + N^2 + W` --- where W is `nums[max] - nums[min]`. This algorithm is good for multiple requeries with different k values on the same array, and arrays whose element values are not too far apart.

Approach 2: put the distances into a heap, starting from the smallest ones. Each neighboring pair (i, j) can have 'children' (i-1, j) and (i, j+1). Keep popping the smallest distance, and adding its children, until we get to the kth. Time: `NlogN <to sort> + N <to heapify> + 2 * (log1 + log2 + ... + log2k)`, which is less than or equal to `NlogN + 4k * log2k`, and k can be up to `O(N^2)`. This algorithm is good for small ks.

Approach 3: from a list of sorted distances -- for each distance X we calculate the number of pairs with distance less or equal to X, and we use binary search to search for the smallest value >= k. To calculate the number of pairs with distances <= a value, use sliding window -- for each pair that ends with index 'right', move the left pointer until the distance is small enough. Time: `NlogN + NlogW`.

### # Code (Python)

Approach 1:

``````class Solution:
def smallestDistancePair1(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def smallestDistancePair(self, nums, k):
nums.sort()
distances = [0 for _ in range(nums[-1] - nums[0] + 1)]
for i in range(1, len(nums)):
for j in range(i):
distances[nums[i]-nums[j]] += 1
distances_so_far = 0
for bucket_index in range(len(distances)):
distances_so_far += distances[bucket_index]
if distances_so_far >= k:
return bucket_index
``````

Approach 2:

``````import heapq
class Solution:
def smallestDistancePair(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
#(distance, index1, index2) --> in heap
#(index1, index2) --> in set (to dedup)
nums.sort()
heap = [(nums[i] - nums[i-1], i - 1, i) for i in range(1, len(nums))]
heapq.heapify(heap)
explored_pairs = set([(i-1, i) for i in range(1, len(nums))])
for i in range(k):
distance, index1, index2 = heapq.heappop(heap)
if i == k - 1:
return distance
self._add_pair((index1, index2 + 1), heap, explored_pairs, nums)
self._add_pair((index1 - 1, index2), heap, explored_pairs, nums)

def _add_pair(self, pair, heap, explored, nums):
if pair[0] >= 0 and pair[1] < len(nums) and pair not in explored:
heapq.heappush(heap, (nums[pair[1]] - nums[pair[0]], pair[0], pair[1]))
explored.add(pair)
``````

Approach 3:

``````    def smallestDistancePair(self, nums, k):
nums.sort()
left, right = min([nums[i] - nums[i-1] for i in range(1, len(nums))]), nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
if self._num_pairs_with_distance_less_or_equal(nums, mid) >= k:
right = mid
else:
left = mid + 1
return left

def _num_pairs_with_distance_less_or_equal(self, nums, target_distance):
count = 0
left = 0
for right in range(1, len(nums)):
while nums[right] - nums[left] > target_distance:
left += 1
count += right - left
return count
``````

### # Code (C++)

Approach 1:

Approach 2:

``````
``````