codingpineapple

Posted on

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

### 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;
};
``````