719. Find K-th Smallest Pair Distance

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: nums = [1,3,1], k = 1 Output: 0

Input: nums = [1,1,1], k = 2 Output: 0

Input: nums = [1,6,1], k = 3 Output: 5

Solution Approach

The provided solution utilizes binary search combined with two pointers to efficiently find the kth smallest pair distance within the given array of integers.

Algorithm

1. Sort the Array: Initially, sort the input array nums. Sorting the array helps in identifying the distances between pairs efficiently.

2. Define a Count Function: Create a function count(mid) to count the number of pairs with a distance less than or equal to mid. This function utilizes two pointers to traverse the sorted array and efficiently counts such pairs.

3. Apply Binary Search: Utilize binary search over the range of possible distances (from 0 to nums[-1] - nums[0]) to find the kth smallest distance. The binary search determines the value of mid such that the count of pairs with distance less than or equal to mid is equal to k. This efficiently narrows down the range of possible distances until the kth smallest distance is found.

Implement

    class Solution:
      def smallestDistancePair(self, nums: List[int], k:int) -> int:
          def count(mid):
              cnt = i = 0
              for j, num in enumerate(nums):
                  while num - num[i] > mid:
                      i += 1
                  cnt += j - i
              return cnt
      nums.sort()
      return bisect_left(range(nums[-1] - nums[0]), k, key = count)
         
      

    
    

Twitter  facebook  Email