Here, We see Find K-th Smallest Pair Distance LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Find K-th Smallest Pair Distance LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Find K-th Smallest Pair Distance LeetCode Solution
Table of Contents
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
Find K-th Smallest Pair Distance LeetCode Solution 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];
}
};
Code language: PHP (php)
Find K-th Smallest Pair Distance LeetCode Solution 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;
}
}
Code language: PHP (php)
Find K-th Smallest Pair Distance Solution 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;
}
}
};
Code language: JavaScript (javascript)
Find K-th Smallest Pair Distance Solution 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
Code language: HTML, XML (xml)