LC 0719 [H] Find K th Smallest Pair Distance - ALawliet/algorithms GitHub Wiki

https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/769705/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems.

Very similar to LC 668 above, both are about finding Kth-Smallest. Just like LC 668, We can design an enough function, given an input distance, determine whether there're at least k pairs whose distances are less than or equal to distance. We can sort the input array and use two pointers (fast pointer and slow pointer, pointed at a pair) to scan it. Both pointers go from leftmost end. If the current pair pointed at has a distance less than or equal to distance, all pairs between these pointers are valid (since the array is already sorted), we move forward the fast pointer. Otherwise, we move forward the slow pointer. By the time both pointers reach the rightmost end, we finish our scan and see if total counts exceed k.

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        # count enough pairs where distance difference is at least k
        def enough(distance):  # two pointers
            count = 0
            l = 0
            r = 0
            while l < n or r < n:
                while r < n and nums[r] - nums[l] <= distance:
                    r += 1 # move fast ptr
                count += r - l - 1 # window len
                l += 1 # move slow ptr
            return count >= k # when we have counted enough valid pairs, we can stop searching

        nums.sort()
        # leftmost binary search
        n = len(nums)
        l = 0
        r = nums[-1] # nums[-1] - nums[0], max(nums) - min(nums)
        while l < r:
            m = (l + r) // 2
            if not enough(m):
                l = m + 1
            else:
                r = m
        return l # select kth smallest