Problem statement

https://binarysearch.com/problems/Kth-Pair-Distance/

Solution

Equal to Leetcode 0719 Find K-th Smallest Pair Distance.

Complexity

Time complexity is O(n log n + n log M), space is O(n).

Code

class Solution:
    def solve(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