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