Leetcode Daily Question 14/08/2024 - 719. Find K-th Smallest Pair Distance

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

from typing import List
class Solution:
  def smallestDistancePair(self, nums: List[int], k:int) -> int:
    nums.sort()
    def countPairs(target):
      count = 0 
      left = 0 
      for right in range(len(nums)):
        while nums[right] - nums[left] > target:
          left += 1
        count += (right - left)
      return count
    
    left = 0
    right = nums[-1] - nums[0]
    while left < right:
      mid = (left + right) // 2
      if countPiars(mid) < k:
        left = mid + 1
      else:
        right = mid
    return left

Explanation:

My first thoughts to solving this question involved finding out all differences and using a min heap to find the kth smallest distance. However, this is extremely time inefficient.

Then, I thought of using binary search to speed up the search. The idea is to count the number of distances less than a given target. This way, if this count is less than k, then the kth smallest distance must be larger than the target and we move our least distance to where mid is.

To find the number of distances less than a target, we can use the two pointer technique. We use the right pointer to traverse the array to define our right hand bound.

Then, we check if the difference between nums[right] and nums[left] is greater than our target. If so, we increment left and try again until we find the smallest element such that nums[right] - nums[left] <= target. The number of pair-distances satisfying this must then be right - left.

def countPairs(target):
  left = 0
  count = 0
  for right in range(len(nums)):
    while nums[right] - nums[left] > target:
      left += 1
    count += (right - left)
  return count

To set up binary search, we set left to be the minimal pair-distance possible (which is 0 by default), and right to be the maximal. That is, the difference between the right most and left most element element in nums (we sorted nums in the beginning).

We then use our helper function to find the kth smallest pair distance.

def smallestDistancePair(nums, k):
  nums.sort()
  left = 0
  right = nums[-1] - nums[0]
  while left < right:
    mid = (left + right) // 2
    if countPairs(mid) < k:
      left = mid + 1
    else:
      right = mid
  return left

The full solution can be found near the top of this page.