Leetcode 719. Find K-th Smallest Pair Distance

Question

The question statement is as follows- Given an integer array, return the kth smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

The solution which leetcode accepts is the Binary Search + Prefix Sum Approach. But even after going through it more than 100 times, I am not able to figure it out.

Can someone guide me? Possibly with a dry run of an example and help me figure out how are we actually eliminating the search space using binary search? Please help me with an example as there are ample descriptive explanations on the internet

Answer 1

This is a LeetCode hard-tagged problem, you can see the explanations of various solutions here in this link:

Python

class Solution:
    def smallestDistancePair(self, nums, k):
        def count(arr, val):
            res = 0
            for i in range(len(arr)):
                res += bisect.bisect_right(arr, arr[i] + val, lo=i) - i - 1
            return res

        nums.sort()
        lo = min(abs(nums[i] - nums[i + 1]) for i in range(len(nums) - 1))
        hi = abs(nums[0] - nums[~0])
        while lo < hi:
            mid = (lo + hi) // 2
            if count(nums, mid) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

Java

class Solution {
    private int upperBound(int[] nums, int lo, int hi, int key) {
        if (nums[hi] <= key)
            return hi + 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key >= nums[mid])
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }

    private int countPairs(int[] nums, int mid) {
        int length = nums.length;
        int res = 0;
        for (int i = 0; i < length; i++)
            res += upperBound(nums, i, length - 1, nums[i] + mid) - i - 1;
        return res;
    }

    public int smallestDistancePair(int[] nums, int k) {
        int length = nums.length;
        Arrays.sort(nums);
        int lo = nums[1] - nums[0];
        for (int i = 1; i < length - 1; i++)
            lo = Math.min(lo, nums[i + 1] - nums[i]);

        int hi = nums[length - 1] - nums[0];

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (countPairs(nums, mid) < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
}

C++

#include <vector>
#include <algorithm>

static const struct Solution {
    static const int smallestDistancePair(
        const std::vector<int> &nums, 
        const int k
    ) {
        std::vector<int> copy_nums = nums;
        std::sort(copy_nums.begin(), copy_nums.end());
        const int length = copy_nums.size();
        int lo = 0;
        int hi = 1e6;

        while (lo < hi) {
            const int mid = lo + (hi - lo) / 2;
            int count = 0;

            for (int i = 0, j = 0; i < length; i++) {
                while (j < length and copy_nums[j] - copy_nums[i] <= mid) {
                    j++;
                }

                count += j - i - 1;
            }

            if (count < k) {
                lo = mid + 1;

            } else {
                hi = mid;
            }
        }

        return lo;
    }
};