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
Constraints:
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2class Solution {
private class FixedBufferPQ {
int k; // Fixed size of buffer
Queue<Integer> pq;
public FixedBufferPQ(int k) {
this.k = k;
pq = new PriorityQueue<>((a, b) -> b - a);
}
public boolean add(int x) {
if (pq.size() == k) {
if (x > pq.peek())
return true;
pq.poll();
}
pq.offer(x);
return false;
}
public int top() {
if (pq.isEmpty())
return -1;
return pq.peek();
}
}
public int smallestDistancePair(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
FixedBufferPQ fpq = new FixedBufferPQ(k);
for (int step = 1; step < n; step++)
for (int i = 0; i < n - step; i++)
if (fpq.add(nums[i + step] - nums[i])) {
step++;
i = 0;
}
return fpq.top();
}
}