Leetcode 719. Find K-th Smallest Pair Distance
Problem Explanation
In this problem, we are given an integer array and an integer k. We first find out all the possible pairs in the array and calculate their absolute difference. We then sort these differences, and the kth smallest difference is our required output.
Let's consider an example:
1nums = [1,3,1], k = 1.
All the pairs are (1,3), (1,1), (3,1) with differences of 2, 0, 2 respectively. After sorting these, we get [0, 2, 2]. The 1st smallest difference is 0.
Solution Approach
The solution uses a binary search algorithm to effectively find the kth smallest difference. The binary range is defined by the difference between maximum and minimum element in the sorted array.
The function pairDistancesNoGreaterThan() is used to find the number of pair distances that are no greater than a given difference. The more the difference, the more count we will get.
The solution starts by calculating the binary mid value and count the differences no greater than the mid value. If the count is greater than or equal to k, it means that we got more or equal needed number of differences, so the required difference could be mid or less, so we continue to search in the left half of the binary search. Otherwise, we look for more in the right half.
Finally, the binary search terminates at the smallest difference where the count of differences is >= k.
Let's walk through this with an example:
Given nums = [1,3,1], k = 1, we start by sorting the array to get [1,1,3]. Then we apply binary search with l = 0
and r = 3 - 1 = 2
. The binary mid value, m = 1
, we then call pairDistancesNoGreaterThan(nums, m) function to get count = 2 pair distances <= 1. Since 2 >= 1, we continue with the next binary search by setting r = m = 1
. We get new mid value m = 0
and call pairDistancesNoGreaterThan(nums, m) function to get count = 1 pair distances <= 0. This is the exact count we need so the function returns 0 as kth smallest difference.
Solutions
Python Solution
1 2python 3class Solution: 4 def smallestDistancePair(self, nums, k): 5 def pairDistancesNoGreaterThan(nums, m): 6 count = 0 7 j = 1 8 for i in range(len(nums)): 9 while j < len(nums) and nums[j] <= nums[i] + m: 10 j += 1 11 count += j - i - 1 12 return count 13 14 nums.sort() 15 l = 0 16 r = nums[-1] - nums[0] 17 18 while l < r: 19 m = (l + r) // 2 20 if pairDistancesNoGreaterThan(nums, m) >= k: 21 r = m 22 else: 23 l = m + 1 24 25 return l
Java Solution
1 2java 3class Solution { 4 public int smallestDistancePair(int[] nums, int k) { 5 Arrays.sort(nums); 6 int l = 0, r = nums[nums.length - 1] - nums[0]; 7 while (l < r) { 8 int m = (l + r) / 2; 9 int count = pairDistancesNoGreaterThan(nums, m); 10 if (count >= k) 11 r = m; 12 else 13 l = m + 1; 14 } 15 return l; 16 } 17 18 private int pairDistancesNoGreaterThan(int[] nums, int m) { 19 int count = 0, j = 1; 20 for (int i = 0; i < nums.length; ++i) { 21 while (j < nums.length && nums[j] <= nums[i] + m) 22 ++j; 23 count += j - i - 1; 24 } 25 return count; 26 } 27}
JavaScript Solution
1 2javascript 3class Solution { 4 smallestDistancePair(nums, k) { 5 nums.sort((a, b) => a - b); 6 let l = 0, r = nums[nums.length - 1] - nums[0]; 7 8 while (l < r) { 9 let m = Math.floor((l + r) / 2); 10 let count = this.pairDistancesNoGreaterThan(nums, m); 11 if (count >= k) 12 r = m; 13 else 14 l = m + 1; 15 } 16 17 return l; 18 } 19 20 pairDistancesNoGreaterThan(nums, m) { 21 let count = 0; 22 let j = 1; 23 for (let i = 0; i < nums.length; ++i) { 24 while(j < nums.length && nums[j] <= nums[i] + m) 25 ++j; 26 count += j - i - 1; 27 } 28 return count; 29 } 30}
C++ Solution
1
2cpp
3class Solution {
4public:
5 int smallestDistancePair(vector<int>& nums, int k) {
6
7 sort(nums.begin(), nums.end());
8 int l = 0, r = nums.back() - nums.front();
9 while (l < r) {
10 int m = (l + r) / 2;
11 if (pairDistancesNoGreaterThan(nums, m) >= k)
12 r = m;
13 else
14 l = m + 1;
15 }
16 return l;
17 }
18
19private:
20 int pairDistancesNoGreaterThan(vector<int>&nums, int m) {
21 int count = 0, j = 1;
22 for (int i = 0; i < nums.size(); ++i) {
23 while(j < nums.size() && nums[j] <= nums[i] + m)
24 ++j;
25 count += j - i - 1;
26 }
27 return count;
28 }
29};
C# Solution
1 2csharp 3public class Solution { 4 public int SmallestDistancePair(int[] nums, int k) { 5 Array.Sort(nums); 6 int l = 0; 7 int r = nums[nums.Length - 1] - nums[0]; 8 while (l < r) { 9 int m = l + (r - l) / 2; 10 if (PairDistancesNoGreaterThan(nums, m) >= k) 11 r = m; 12 else 13 l = m + 1; 14 } 15 return l; 16 } 17 18 private int PairDistancesNoGreaterThan(int[] nums, int m) { 19 int count = 0; 20 int j = 0; 21 for (int i = 0; i < nums.Length; ++i) { 22 while(nums[j] <= nums[i] + m) 23 ++j; 24 count += j - i - 1; 25 } 26 return count; 27 } 28}
In these solutions, we first sort the array and then use the binary search method to find the kth smallest difference. The time complexity of this solution is O(nlogn) and the space complexity is O(1). The sorting takes O(nlogn) and the binary search takes O(nlogr) where r is the range of differences.### Ruby Solution
1 2ruby 3class Solution 4 def smallestDistancePair(nums, k) 5 nums.sort! 6 l = 0 7 r = nums[-1] - nums[0] 8 9 while l < r 10 m = (l + r) / 2 11 count = pairDistancesNoGreaterThan(nums, m) 12 if count >= k 13 r = m 14 else 15 l = m + 1 16 end 17 end 18 return l 19 end 20 21 def pairDistancesNoGreaterThan(nums, m) 22 count = 0 23 j = 1 24 for i in 0...nums.length 25 while j < nums.length and nums[j] <= nums[i] + m 26 j += 1 27 end 28 count += j - i - 1 29 end 30 return count 31 end 32end
In this Ruby solution, we first sort the array using the sort! method, which sorts the array in place. Then, we use the binary search algorithm to find the kth smallest pair distance. The function pairDistancesNoGreaterThan checks the number of pair distances no greater than the given value, m. Depending on the result, we adjust our binary search space to either the left or right half. We repeat this process until l is not less than r. The final result is then returned as the kth smallest pair distance.
The time complexity of this solution is the same as the others, O(nlogn), due to the sorting and binary search operations. As we are not creating any new data structures, apart from the input array, the space complexity remains at O(1).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.