Find K-th Smallest Pair Distance

Leetcode Problem:

• Find K-th Smallest Pair Distance

Summary

• Find the kth smallest distance among all pairs of integers in an array.

Approach

• Binary Search: The solution uses a binary search approach to find the kth smallest distance
• It sorts the array and then uses two pointers (l and r) to represent the range of possible distances
• The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
• If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
• Otherwise, it moves the left pointer to the right.

Complexity

• O(N log N + log k) where N is the length of the array
• The sorting operation takes O(N log N) time, and the binary search takes O(log k) time.

Explain

• The solution first sorts the array in ascending order
• It then initializes two pointers, l and r, to represent the range of possible distances
• The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
• If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
• Otherwise, it moves the left pointer to the right
• The solution repeats this process until the left pointer is greater than the right pointer
• The final answer is the smallest distance that results in k pairs.

Solution Code:

class Solution {
public:
    int smallestDistancePair(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int N = nums.size();
        int l = 0;
        int r = 1000000;
        int ans = 0;
        while(l <= r ){
            int mid = (l + r) / 2;
            int left = 0;
            int right = 0;
            int cnt = 0;
            int beforeRight = 0;
            while(right < N){
                while(right < N && nums[right] - nums[left] <= mid){
                    right++;
                }
                int NN = right - left;
                cnt += (NN * (NN-1))/2;
                if (left != 0){
                    NN = (beforeRight - left);
                    cnt -= (NN * (NN-1))/2;
                }
                beforeRight = right;
                while(left < right && nums[right] - nums[left] > mid){
                    left++;
                }
            }
            if (cnt >= k){
                if (cnt == k){
                    ans = mid;
                }
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        return ans;
    }
};