[Leetcode] 719. Find K-th Smallest Pair Distance

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

initial

so coming from the previous BS question, it was a similar question. I was thinking how to count number of pairs efficiently, rather than the obv n^2 double for loop.

I kept thinking but couldnt. Actually lets observe a sorted list. [1, 1, 5, 6], target =3

if nums[j]-nums[i]<target, then any number in between i, i+1, ... j-1 can pair with j to have a pair difference that is < target. This is cuz i is the largest leftmost number that fits this condition so any number in between will also definitely fit this condition.

So its a two pointer!

sol

very careful optimisation is do not reset left pointe for each right iteration. If the previous left index is invalid, it will continue to stay invalid for next iterations of right pointer.

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def check(guess):
            total=0
            left=0
            for right in range(len(nums)):
                while nums[right]-nums[left]>guess and left<right:
                    left+=1
                total+=right-left
            return total
        left,right=-1,int(10e8)
        nums.sort()
        while left<right:
            mid = left+(right-left)//2
            if check(mid)>=k:
                right=mid
            else:
                left=mid+1
        return left

complexity

n log n log (range) n cuz of right iteration

close but sort is a separate time complexity so Total Time Complexity: O(n log n + log(range) × n) = O(n log n + n log(range))

1 space