Given an integer array nums and integer k, return the kth smallest value of |nums[i] - nums[j]| for all pairs (i, j) with i < j.
Input: nums=[1,3,1], k=1 → Output: 0Input: nums=[1,1,1], k=2 → Output: 0
Sort array. Binary search on the answer (pair distance). Count pairs with distance <= mid using sliding window.
- Sort nums. lo=0, hi=nums[n-1]-nums[0].
- For mid: count pairs with distance <= mid using two pointers.
- If count >= k: hi=mid. Else lo=mid+1.
import java.util.Arrays;
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length, lo = 0, hi = nums[n-1] - nums[0];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0, left = 0;
for (int right = 0; right < n; right++) {
while (nums[right] - nums[left] > mid) left++;
count += right - left;
}
if (count >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
}
- Time Complexity: O(N log N + N log W) where W=max distance
- Space Complexity: O(1)