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