Problem statement

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

Solution

Let us ask a question: given sorted list of numbers, how many pairs we have, such that their difference <= x, where x some given number. We can solve this question, using BS in O(n log n), but actually we can use two pointers approach to solve it in O(n). Then we do binary search in range [0, M], where M is the biggest number, asking question: how many pairs with difference <= x we have.

Complexity

Overall complexity is O(n log n + n log M).

Code

class Solution:
    def smallestDistancePair(self, nums, k):
        def helper(x):
            count, left = 0, 0
            for right, num in enumerate(nums):
                while num - nums[left] > x:
                    left += 1
                count += right - left
            return count >= k

        nums.sort()
        beg, end = 0, nums[-1] - nums[0]
        while beg < end:
            mid = (beg + end) // 2
            if helper(mid):
                end = mid
            else:
                beg = mid + 1

        return beg