719.md

719. Find K-th Smallest Pair Distance

Solution 1 (time O(nlog(max(nums))), space O(1))

class Solution(object):
    def smallestDistancePair(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def check(nums, x):
            n = len(nums)
            ret = 0
            p = 1
            for i in range(n):
                while p < n and nums[p] - nums[i] <= x:
                    p += 1
                ret += (p - i - 1)
            return ret

        nums.sort()
        left = 0
        right = int(1e6)
        while left < right:
            mid = (left + right) / 2
            if check(nums, mid) >= k:
                right = mid
            else:
                left = mid + 1
        return right