LeetCode 719. Find K-th Smallest Pair Distance (javascript solution)
codingpineapple
Posted on May 16, 2021
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;
};
π πͺ π
π©
codingpineapple
Posted on May 16, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
sorting Recap the highlight of the sorting algorithms using JavaScript for beginners
October 5, 2024
datastructures DSA with JS: Understanding Custom Array Data Structure in JavaScript - A Step-by-Step Guide
September 29, 2024