Last updated on January 29th, 2025 at 02:12 am
Here, we see a Find K-th Smallest Pair Distance LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Binary Search, Heap
Companies
Level of Question
Hard
Find K-th Smallest Pair Distance LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is Modified Binary Search. This pattern is evident in the Java, JavaScript, and Python implementations, where the solution involves searching for the smallest distance pair using a binary search approach on the possible range of distances. The C++ implementation uses a Brute Force with Sorting approach.
3. Code Implementation in Different Languages
3.1 Find K-th Smallest Pair Distance C++
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int n = nums.size();
vector<int>res;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
res.push_back(abs(nums[i]-nums[j]));
}
}
sort(res.begin(),res.end());
return res[k-1];
}
};
3.2 Find K-th Smallest Pair Distance Java
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int minDist = 0;
int maxDist = nums[nums.length - 1] - nums[0];
while(minDist <= maxDist) {
int midDist = minDist + (maxDist - minDist)/2;
int left = 0;
int right = 0;
int count = 0;
while(right < nums.length) {
if(nums[right] - nums[left] > midDist) {
left++;
} else {
count += right - left;
right++;
}
}
if(count >= k) {
maxDist = midDist - 1;
} else {
minDist = midDist + 1;
}
}
return minDist;
}
}
3.3 Find K-th Smallest Pair Distance JavaScript
var cntPairsOfDistanceUnderN = function(nums, n) {
let lt = 0;
let rt = 1;
let cnt = 0;
while (lt <= rt) {
if (lt === rt) {
rt++;
}
if (rt === nums.length) {
cnt = cnt + ((rt - lt - 1) * (rt - lt)) / 2;
break;
}
if (Math.abs(nums[rt] - nums[lt]) < n) {
rt++;
} else {
cnt = cnt + (rt - lt - 1);
lt++;
}
}
return cnt;
};
var smallestDistancePair = function(nums, k) {
nums.sort((a, b) => a - b);
let lt = 0;
let rt = 1000000;
while (lt <= rt) {
let mid = Math.floor((lt + rt) / 2);
const a = cntPairsOfDistanceUnderN(nums, mid);
const b = cntPairsOfDistanceUnderN(nums, mid + 1);
if (a < k && b >= k) {
return mid;
} else if (b < k) {
lt = mid + 1;
} else {
rt = mid - 1;
}
}
};
3.4 Find K-th Smallest Pair Distance Python
class Solution(object):
def smallestDistancePair(self, nums, k):
nums.sort()
n = len(nums)
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = left + (right - left) // 2
start = 0
count = 0
for i in range(n):
while nums[i] - nums[start] > mid:
start += 1
count += i - start
if count < k:
left = mid + 1
else:
right = mid
return left
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n² log n) | O(n²) |
| Java | O(n log n + n log(maxDist)) | O(1) |
| JavaScript | O(n log n + n log(maxDist)) | O(1) |
| Python | O(n log n + n log(maxDist)) | O(1) |
- The C++ implementation is inefficient compared to the other implementations due to its brute-force approach.
- The Java, JavaScript, and Python implementations are optimized using the Modified Binary Search pattern, which significantly reduces the time complexity compared to the brute-force approach.
- The space complexity for the optimized implementations is O(1), as they do not use additional data structures to store intermediate results.