Leetcode 719 Solution

This article provides solution to leetcode question 719 (find-k-th-smallest-pair-distance)
Categories:
Tags:
Access this page by simply typing in "lcs 719" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-k-th-smallest-pair-distance

Solution

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def getSmallerPairs(nums, diff):
            l = 0
            r = 1
            ans = 0
            while r < len(nums):
                if nums[r] - nums[l] > diff:
                    l += 1
                else:
                    ans += r - l
                    r += 1
            return ans

        nums.sort()

        l = 0
        r = nums[-1] - nums[0]
        while l < r:
            m = (l + r) // 2
            if getSmallerPairs(nums, m) >= k:
                r = m
            else:
                l = m + 1
        return l