Leetcode: 719. Find K-th Smallest Pair Distance

Can we state the problem as result of multiple searches? Use a Binary Search to find the value of the \(k\)th smallest pair distance. To verify if the value \(a\) is a valid answer, count the number of pairs starting on \(i\): \(j - i - 1\) where \(nums[j] < nums[i] + a\). The value for \(j\) can be found using a second Binary Search. Time complexity is \(O(n \log n \log m)\) where \(m=max(nums) - min(nums)\). Space complexity is \(O(1)\).

from typing import List


class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        N = len(nums)
        nums.sort()

        def check(delta):
            cur = 0
            for i in range(N):
                j = bisect_right(nums, nums[i] + delta, lo=i)
                cur += j - i - 1
            return cur >= k

        lo = 0
        hi = nums[-1] - nums[0]
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if check(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo