LeetCode 719. Find K-th Smallest Pair Distance (javascript solution)

#algorithms #javascript

Description:

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

Solution:

Time Complexity : O(nlog(n))
Space Complexity: O(1)

// Binary search + sliding window
var smallestDistancePair = function(nums, k) {
    nums.sort((a,b) => a-b);
    let lo = 0;
    let hi = nums[nums.length - 1] - nums[0];

    while (lo < hi) {
        let mi = lo + Math.floor((hi-lo) / 2);
        // Sliding window
        let count = 0, left = 0;
        for (let right = 1; right < nums.length; ++right) {
            // Keep moving left pointer until we reach a difference between two pointers that is less than mi
            while (nums[right] - nums[left] > mi) left++;
            // Add the amount of pairs in the window to the count
            count += right - left;
        }
        //count = number of pairs with distance <= mi
        if (count >= k) hi = mi;
        else lo = mi + 1;
    }
    return lo;
};