Find K Th Smallest Pair Distance - Leetcode Solution

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.

1