In this guide, you will get 719. Find K-th Smallest Pair Distance LeetCode Solution with the best time and space complexity. The solution to Find K-th Smallest Pair Distance problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find K-th Smallest Pair Distance
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
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 distance pair is (1,1), and its distance is 0.
Example 2:
Input: nums = [1,1,1], k = 2
Output: 0
Example 3:
Input: nums = [1,6,1], k = 3
Output: 5
Constraints:
n == nums.length
2 <= n <= 104
0 <= nums[i] <= 106
1 <= k <= n * (n – 1) / 2
Complexity Analysis
Time Complexity: O(\texttt{sort}) + O(n\log (\max(\texttt{nums}) – \min(\texttt{nums})))
Space Complexity: O(\texttt{sort})
719. Find K-th Smallest Pair Distance LeetCode Solution in C++
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
ranges::sort(nums);
int l = 0;
int r = nums.back() - nums.front();
while (l < r) {
const int m = (l + r) / 2;
if (numPairDistancesNoGreaterThan(nums, m) >= k)
r = m;
else
l = m + 1;
}
return l;
}
private:
int numPairDistancesNoGreaterThan(const vector<int>& nums, int m) {
int count = 0;
int j = 1;
// For each index i, find the first index j s.t. nums[j] > nums[i] + m,
// so numPairDistancesNoGreaterThan for the index i will be j - i - 1.
for (int i = 0; i < nums.size(); ++i) {
while (j < nums.size() && nums[j] <= nums[i] + m)
++j;
count += j - i - 1;
}
return count;
}
}; /* code provided by PROGIEZ */
719. Find K-th Smallest Pair Distance LeetCode Solution in Java
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int l = 0;
int r = nums[nums.length - 1] - nums[0];
while (l < r) {
final int m = (l + r) / 2;
if (numPairDistancesNoGreaterThan(nums, m) >= k)
r = m;
else
l = m + 1;
}
return l;
}
private int numPairDistancesNoGreaterThan(int[] nums, int m) {
int count = 0;
int j = 1;
// For each index i, find the first index j s.t. nums[j] > nums[i] + m,
// so numPairDistancesNoGreaterThan for the index i will be j - i - 1.
for (int i = 0; i < nums.length; ++i) {
while (j < nums.length && nums[j] <= nums[i] + m)
++j;
count += j - i - 1;
}
return count;
}
} // code provided by PROGIEZ
719. Find K-th Smallest Pair Distance LeetCode Solution in Python
class Solution:
def smallestDistancePair(self, nums: list[int], k: int) -> int:
nums.sort()
def numPairDistancesNoGreaterThan(m: int) -> int:
count = 0
j = 1
# For each index i, find the first index j s.t. nums[j] > nums[i] + m,
# so numPairDistancesNoGreaterThan for the index i will be j - i - 1.
for i, num in enumerate(nums):
while j < len(nums) and nums[j] <= num + m:
j += 1
count += j - i - 1
return count
return bisect.bisect_left(range(nums[-1] - nums[0]), k,
key=numPairDistancesNoGreaterThan) # code by PROGIEZ
