# 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: