Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have solved the problem of finding the K-th smallest pair distance. This involve the concept of Binary Search.
PROBLEM STATEMENT
The kth smallest distance between a pair of integers a and b can be defined as the absolute difference between a and b.
Suppose you have an array of integers called nums and an integer k. Your task is to find the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
EXAMPLE
Example 1:
Input: nums = [1,2,4,5,6], k = 3
Output: 1
Explanation: The pairs of integers in this array and their distances are as follows:
(1,2) --> |1-2|=1
(1,4) --> |1-4|=3
(1,5) --> |1-5|=4
(1,6) --> |1-6|=5
(2,4) --> |2-4|=2
(2,5) --> |2-5|=3
(2,6) --> |2-6|=4
(4,5) --> |4-5|=1
(4,6) --> |4-6|=2
(5,6) --> |5-6|=1
The kth smallest distance is 1, since there are three pairs with a distance of 1: (1,2), (4,5), and (5,6).
Example 2:
Input: nums = [1,3,1], k = 2
Output: 2
Explanation: There are only two pairs of integers in this array: (1,3) and (1,1). The distances between these pairs are |1-3|=2 and |1-1|=0, respectively. Since we're looking for the second smallest distance and 0 is already the smallest, we must take the next smallest distance, which is 2.
Approach
To solve the problem of finding the kth smallest distance among all pairs of integers in the given array, we can use binary search on the possible range of distances.
First, we sort the input array in ascending order and set the lower and upper bounds for the range of distances. Then, we perform binary search on the range of possible distances by checking the number of pairs in the array with a distance less than or equal to the mid value.
If the number of pairs with a distance less than or equal to mid is less than k, we adjust the lower bound to mid + 1. Otherwise, we adjust the upper bound to mid. We continue the binary search until the lower and upper bounds converge to a single value, which will be the kth smallest distance. Finally, we return this value.
BRUTE FORCE APPROACH
The approach involves sorting the input array and performing binary search on the range of possible distances. We count the number of pairs in the array with a distance less than or equal to the mid value and adjust the bounds accordingly until the kth smallest distance is found.
Algorithm
- Sort the input array in ascending order.
- Set the lower and upper bounds for the range of distances.
- Perform binary search on the range of possible distances by checking the number of pairs in the array with a distance less than or equal to the mid value.
- If the number of pairs with a distance less than or equal to mid is less than k, adjust the lower bound to mid + 1. Otherwise, adjust the upper bound to mid.
- Continue the binary search until the lower and upper bounds converge to a single value, which will be the kth smallest distance.
- Return the kth smallest distance.
Implement Code
class Solution {
public int smallestDistancePair(int[] nums, int k) {
int n = nums.length;
int[] distances = new int[n * (n - 1) / 2];
int z = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
distances[z++] = Math.abs(nums[i] - nums[j]);
}
}
Arrays.sort(distances);
return distances[k - 1];
}
}
Time Complexity : O(n^2)
Space Complexity : O(1)
Explanation
We first calculates all possible distances between pairs of integers in the array and stores them in a separate array called "distances".
We then sorts the "distances" array in ascending order.
Finally, it returns the kth smallest distance by accessing the element at index k-1 in the sorted "distances" array.
For example, consider an input array nums = [1, 3, 5] and k = 3. The possible distances between pairs of integers in the array are [2, 4, 2]. The "distances" array is constructed as [2, 4, 2] and sorted to [2, 2, 4]. The third smallest distance is 4, which is returned by the function.
Binary Search Approach
Algorithm
- The kth distance must be within the range of [0, max-min] since all numbers are non-negative.
- Perform binary search on this range until lo and hi converge.
- Narrow the search using the count(nums, mi) function that returns the number of distances less than or equal to mi.
- If count(mi) is smaller than k, set lo = mi + 1. Otherwise, set hi = mi.
- The count(nums, mi) function can be implemented efficiently using the sliding window method with two pointers.
Implement Code
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int lo = 0, hi = nums[nums.length - 1] - nums[0];
while (lo != hi) {
int mi = lo + (hi - lo) / 2;
if (count(nums, mi) < k) lo = mi + 1;
else hi = mi;
}
return lo;
}
private int count(int[] nums, int d) {
int right = 1;
int count = 0;
while (right < nums.length) {
int left = 0;
while (nums[right] - nums[left] > d) left++;
count += right - left;
right++;
}
return count;
}
}
time complexity : O(nlogn + n^2logw), where w = max-min.
space complexity : O(1)
Explanation
Let's consider an example to understand the given code:
Suppose we have an input array nums = [1, 3, 5, 7, 9] and k = 3.
- The code first sorts the input array, resulting in nums = [1, 3, 5, 7, 9].
- It initializes two variables, lo = 0 and hi = 9 - 1 = 8, which represent the lower and upper bounds of the range of possible distances between pairs of integers in the array.
- It enters a while loop that continues until lo and hi converge to a single value.
- Inside the while loop, it sets mi to the mid value of the current range using the formula mi = lo + (hi - lo) / 2.
- It then calls the count(nums, mi) function to count the number of distances less than or equal to mi.
- If the count is less than k, it adjusts the lower bound of the range to mi + 1. Otherwise, it adjusts the upper bound of the range to mi.
- The while loop continues until lo and hi converge to a single value, which is the kth smallest distance.
- The code returns the final value of lo, which represents the kth smallest distance.
Now, let's look at the count(nums, d) function: - It initializes two variables, right = 1 and count = 0.
- It enters a while loop that continues until right reaches the end of the array.
- Inside the while loop, it initializes left to 0 and enters another while loop that continues until the difference between nums[right] and nums[left] is less than or equal to d.
- The inner while loop increments left until nums[right] - nums[left] is less than or equal to d.
- Once the inner while loop ends, it adds the number of pairs with right as one endpoint and left as the other endpoint to the count.
- It then increments right and continues to the next iteration of the while loop.
- Finally, it returns the total count of pairs with distances less than or equal to d.
In our example, the count(nums, mi) function is called with mi = 4 during the first iteration of the while loop in smallestDistancePair(). The count(nums, 4) function counts the number of pairs with distances less than or equal to 4 using the sliding window method with two pointers. It returns a count of 5, which is greater than k=3.
Therefore, the upper bound of the range is set to mi = 4.
During the second iteration, count(nums, 2) is called, which counts the number of pairs with distances less than or equal to 2. It returns a count of 2, which is less than k = 3. Therefore, the lower bound of the range is set to mi + 1 = 3.
During the third and final iteration, count(nums, 3) is called, which counts the number of pairs with distances less than or equal to 3. It returns a count of 3, which is equal to k = 3. Therefore, the while loop exits and the function returns the final value of lo, which is 3. Thus, the kth smallest distance is 3.
Conclusion
We have solved the problem "Find K-th Smallest Pair Distance" by understanding brute force and optimising it to get to the binary search solution.
