Solution For Find K Th Smallest Pair Distance

Problem statement:

Given an integer array nums sorted in non-decreasing order, find the kth smallest pair distance.

Pair distance is defined as the absolute difference between two numbers.

Example 1:
Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest pair distance is 0.

Solution approach:

1. The first and basic idea that can be thought of is to generate all the possible pairs and then sort them and finally return the kth distance. But this approach would be of no use as it would have a very high time complexity of O(n^2logn) and would not be suitable for large arrays.

2. Next, we may try to optimize the first idea and sort the array making use of 2 pointers, i and j, where i is the beginning and j is the end of the array. We then iterate through the array while keeping j fixed and move i by 1 to get all the possible pairs. During this process, we keep track of all the pairs and then sort them, and then return the kth distance. But again, the time complexity would still be O(n^2logn).

3. Another approach that can be used to solve this problem is binary search. We first sort the array, and then calculate the maximum and minimum difference between pairs. We then make a binary search to find the mid of the maximum and minimum differences, and check if there are at least k pairs in the array having distances less than or equal to the mid. If yes, we move the right pointer to mid, and check again. If no, we move the left pointer to mid, and continue with this process until we find the kth smallest pair distance.

4. Another approach that can be used to solve this problem is the heap approach. We first sort the array and then trade space for time. We create a heap with the first k elements from the sorted array, and then for each element after k, we push it into the heap while also maintaining k elements in the heap. We then pop the maximum value, and return it as the kth smallest distance.

Solution algorithm:

Here’s the algorithm for the binary search approach.

1. First sort the array.
2. Initialize minimum and maximum difference between pairs as 0 and nums[nums.size()-1]-nums[0] respectively.
3. Run a binary search with minimum=0 and maximum=nums[nums.size()-1]-nums[0].
4. In each iteration of the binary search, calculate mid=minimum+(maximum-minimum)/2
5. For each element in nums, calculate the number of elements that have a distance less than or equal to mid using the two pointer approach.
6. If the number of elements is greater than or equal to k, set maximum to mid.
7. Else, set minimum to mid + 1.
8. Repeat steps 4-7 until minimum is less than maximum.
9. Return minimum.

Solution in python:

class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:

    nums.sort()
    n = len(nums)
    minDiff, maxDiff = 0, nums[n-1] - nums[0]

    while (minDiff < maxDiff):

        mid = (maxDiff + minDiff) // 2
        count, j = 0, 0

        for i in range(n):

            while j < n and nums[j] - nums[i] <= mid:
                j += 1

            count += j - i - 1

        if count >= k:
            maxDiff = mid
        else:
            minDiff = mid + 1

    return minDiff

Time complexity: O(nlogn + nlog(maximum-minimum) + nlogn), where nlogn is due to sorting the array, nlog(maximum-minimum) is due to binary search, and nlogn is due to the nested while loop. This makes the final time complexity of the algorithm to be O(nlog(maximum – minimum)).

Space complexity: O(1).

The above solution makes use of the binary search approach to solve the problem in an optimal time complexity. The other approaches have different time complexities and can also be used to solve this problem.

Step by Step Implementation For Find K Th Smallest Pair Distance

We can solve this problem in Java using the PriorityQueue data structure. We can create a max heap and insert all of the distances into the heap. Then, we can extract the maximum distance k times to find the kth smallest distance.

public int findKthSmallestPairDistance(int[] nums, int k) {
 // create a max heap
 PriorityQueue maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
 // insert all distances into the heap
 for (int i = 0; i < nums.length; i++) {
     for (int j = i + 1; j < nums.length; j++) {
         int distance = Math.abs(nums[i] - nums[j]);
         maxHeap.add(distance);
     }
 }
 // extract the maximum distance k times
 int kthSmallestDistance = 0;
 for (int i = 0; i < k; i++) {
     kthSmallestDistance = maxHeap.poll();
 }
 return kthSmallestDistance;
}

def smallestDistancePair(nums, k):
    
    # sort the array
    nums.sort()
    
    # initialize low and high pointers
    low = 0
    high = 1
    
    # initialize result
    result = 0
    
    # loop until we find the kth smallest distance
    while k > 0:
        
        # update result
        result = nums[high] - nums[low]
        
        # initialize count
        count = 1
        
        # move low pointer to the right until it reaches a value
        # that is not equal to nums[low]
        while low < len(nums) - 1 and nums[low] == nums[low+1]:
            low += 1
        
        # move high pointer to the right until it reaches a value
        # that is not equal to nums[high]
        while high < len(nums) - 1 and nums[high] == nums[high+1]:
            high += 1
        
        # move low pointer to the right by one
        low += 1
        
        # if low pointer is not at the end of the array, move
        # high pointer to the right by one
        if low < len(nums):
            high += 1
        
        # decrement k
        k -= 1
        
    # return result
    return result

//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. 

//Input:
//nums = [1,3,1]
//k = 1
//Output: 0 
//Explanation:
//Here are all the pairs:
//(1,3) -> 2
//(1,1) -> 0
//(3,1) -> 2
//Then the 1st smallest distance pair is (1,1), and its distance is 0.

//Solution:

function findKthSmallestPairDistance(nums, k) {
    
    // sort the array in ascending order
    nums.sort((a, b) => a - b);
    
    // initialize left and right pointers
    let left = 0, right = 1;
    
    // initialize result variable
    let result = 0;
    
    // iterate while right pointer is less than the length of the array
    while (right < nums.length) {
        
        // update result if current distance is less than result
        if (nums[right] - nums[left] < result || k > 1) {
            result = nums[right] - nums[left];
            k--;
        }
        
        // if k becomes 0, break out of the loop
        if (k === 0) {
            break;
        }
        
        // if current distance is greater than result, move left pointer
        if (nums[right] - nums[left] >= result) {
            left++;
        } 
        // if current distance is less than result, move right pointer
        else {
            right++;
        }
    }
    
    // return result
    return result;
}

The following is a C++ solution for the leetcode problem find-k-th-smallest-pair-distance:

int findKthSmallestPairDistance(vector& nums, int k) {
    // sort the array
    sort(nums.begin(), nums.end());
    
    // initialize low and high pointers
    int low = 0, high = nums.size() - 1;
    
    // iterate until low and high pointers meet
    while (low < high) {
        // calculate mid pointer
        int mid = low + (high - low) / 2;
        
        // check if the number of pairs with distance 
        // less than or equal to mid is less than k
        if (countPairs(nums, mid) < k) {
            // if true, update low pointer
            low = mid + 1;
        } else {
            // if false, update high pointer
            high = mid;
        }
    }
    
    // return the final value of low pointer
    return low;
}

// helper function to count number of pairs with 
// distance less than or equal to x
int countPairs(vector& nums, int x) {
    int count = 0;
    
    // initialize left and right pointers
    int left = 0, right = 1;
    
    // iterate over the array
    while (right < nums.size()) {
        // check if the difference between the current 
        // elements is less than or equal to x
        if (nums[right] - nums[left] <= x) {
            // if true, update count
            count += right - left;
            
            // move right pointer one position to the right
            right++;
        } else {
            // if false, move left pointer one position to the right
            left++;
        }
    }
    
    return count;
}

public int SmallestDistancePair(int[] nums, int k) { // Sort the array nums.Sort(); // Initialize low and high pointers int low = 0, high = nums[nums.Length - 1] - nums[0]; // Initialize result result = -1; // Loop until low is less than high while (low < high) { // Get the middle value int mid = low + (high - low) / 2; // Count the number of pairs with distance <= mid int count = CountPairs(nums, mid); // If the count is less than k, that means there are // not enough pairs with distance <= mid and we need // to search for higher values of mid. if (count < k) { low = mid + 1; } // If the count is more than or equal to k, that means // there are enough pairs with distance <= mid and we // need to search for lower values of mid. else { high = mid; result = mid; } } return result; } // Function to count the number of pairs with distance <= mid private int CountPairs(int[] nums, int mid) { int n = nums.Length; int count = 0; // Consider each element as the fixed element. for (int i = 0; i < n - 1; i++) { // Initialize left pointer as the fixed element // and right pointer as the first element // after the fixed element. int left = i, right = i + 1; // Move right pointer until it reaches the end // or finds an element which is greater than the // fixed element. while (right < n && nums[right] - nums[left] <= mid) { right++; } // Get the count of pairs with distance <= mid. count += right - left - 1; } return count; }