# 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:

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.

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

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.

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.

- First sort the array.
- Initialize minimum and maximum difference between pairs as 0 and nums[nums.size()-1]-nums[0] respectively.
- Run a binary search with minimum=0 and maximum=nums[nums.size()-1]-nums[0].
- In each iteration of the binary search, calculate mid=minimum+(maximum-minimum)/2
- 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.
- If the number of elements is greater than or equal to k, set maximum to mid.
- Else, set minimum to mid + 1.
- Repeat steps 4-7 until minimum is less than maximum.
- 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 PriorityQueuemaxHeap = 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; }