719 - binary search

    def smallestDistancePair(self, nums: List[int], k: int) -> int:

        def check(x):
            l = r = count = 0
            n = len(nums)
            while r < n:
                if nums[r] - nums[l] <= x:
                    r += 1
                else:
                    count += (n - r)
                    l += 1
            return n * (n - 1) / 2 - count

        nums.sort()
        l = -1
        r = nums[-1] - nums[0]

        while r - l > 1:
            mid = l + (r - l) // 2
            count = check(mid)
            if count < k:
                l = mid
            else:
                r = mid

        return r