LeetCode Daily: Find K-th Smallest Pair Distance Solution in Java | August 14, 2024

🔍 LeetCode Problem of the Day: Find K-th Smallest Pair Distance

Today, we're solving the "Find K-th Smallest Pair Distance" problem using Java. The task is to find the k-th smallest distance between all possible pairs in a sorted array, using binary search and counting pairs.

👉 Solution: Pinned on the comments

🌟 Problem Description:
This challenge involves finding the k-th smallest absolute difference between all pairs in a given array. The problem is efficiently solved using binary search combined with a two-pointer approach.

🔑 Code Explanation:
Sorting: First, the array is sorted to make pair comparisons easier.
Binary Search: We perform binary search on the possible distance values, which range from 0 to the difference between the maximum and minimum elements.
Counting Pairs: For a given middle distance in binary search, we count how many pairs have a distance less than or equal to this middle value using a two-pointer technique.
Adjustment: Depending on the count, we adjust our binary search range until we narrow down to the k-th smallest distance.

📅 Daily Solutions:
I'm posting solutions to LeetCode daily problems every day. Subscribe and hit the bell icon to stay updated!

👥 Join the Community:
Discuss your solutions in the comments.
Engage with other coders and improve your problem-solving skills.

If this video helped you, please like, share, and subscribe for more daily LeetCode solutions!

#LeetCode #Coding #Programming #TechInterview #BinarySearch #TwoPointers #DailyChallenge #Java

[AlgoXploration]

class Solution {

public int countPairs(int[] nums, int mid) {
int count = 0;
int j = 0;
for(int i = 0; i < nums.length; i++) {
while(j < nums.length && nums[j] - nums[i] <= mid)
j++;
count += j-i-1;
}
return count;
}
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int low = 0;
int high = nums[nums.length-1] - nums[0];


//Here we are applying Binary search
while(low < high) {
int mid = low + (high-low)/2;
int count = countPairs(nums, mid);

if(count < k)
low = mid+1;
else
high = mid;
}
return low;
}
}