Last updated on October 25th, 2024 at 10:24 pm

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

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 1^st 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

1. 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];
    }
};

2. 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;
    }
}

3. 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;
    }
  }
};

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