0719. Find K-th Smallest Pair Distance
https://leetcode.com/problems/find-k-th-smallest-pair-distance
Description
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.length
2 <= n <= 104
0 <= nums[i] <= 106
1 <= k <= n * (n - 1) / 2
ac
class Solution {
public int smallestDistancePair(int[] nums, int k) {
// edge cases
// find min and max
Arrays.sort(nums);
int n = nums.length;
int r = nums[n-1] - nums[0], l = r;
for (int i = 1; i < n; i++) {
l = Math.min(l, nums[i] - nums[i-1]);
}
// binary search
while (l < r) {
int mid = l + (r - l) / 2;
int cnt = countPairs(nums, mid);
if (cnt < k) l = mid + 1;
else r = mid;
}
return l;
}
// how many pairs <= distance
private int countPairs(int[] nums, int distance) {
int res = 0, l = 0;
for (int r = 1; r < nums.length; r++) {
while (nums[r] - nums[l] > distance) {
l++;
}
res += r - l;
}
return res;
}
}
/*
find max/min distance(sort) -> binary search, use sliding window to count pairs
*/
Last updated
Was this helpful?