Solve Daily Problem: 719-kth-smallest Distance

[MuhammadTausif]

719. Find K-th Smallest Pair Distance

Hard

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

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.
Example 2:

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

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

Constraints:

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

[MuhammadTausif]

Solved:

class Solution:
  def smallestDistancePair(self, nums: list[int], k: int) -> int:
    nums.sort()

    def numPairDistancesNoGreaterThan(m: int) -> int:
      count = 0
      j = 1
      # For each index i, find the first index j s.t. nums[j] > nums[i] + m,
      # so numPairDistancesNoGreaterThan for the index i will be j - i - 1.
      for i, num in enumerate(nums):
        while j < len(nums) and nums[j] <= num + m:
          j += 1
        count += j - i - 1
      return count

    return bisect.bisect_left(
        range(0, nums[-1] - nums[0]), k,
        key=lambda m: numPairDistancesNoGreaterThan(m))