## Find K-th Smallest Pair Distance

• Time:O(n\log n) + O(n\log (\max - \min))
• Space:O(1)

## C++

``````class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(begin(nums), end(nums));

int l = 0;
int r = nums.back() - nums.front();

while (l < r) {
const int m = (l + r) / 2;
if (pairDistancesNoGreaterThan(nums, m) >= k)
r = m;
else
l = m + 1;
}

return l;
}

private:
int pairDistancesNoGreaterThan(const vector<int>& nums, int m) {
int count = 0;
int j = 1;
// for each index i, find the first index j s.t. nums[j] > nums[i] + m,
// so pairDistancesNoGreaterThan for index i will be j - i - 1
for (int i = 0; i < nums.size(); ++i) {
while (j < nums.size() && nums[j] <= nums[i] + m)
++j;
count += j - i - 1;
}
return count;
}
};
``````

## JAVA

``````class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);

int l = 0;
int r = nums[nums.length - 1] - nums[0];

while (l < r) {
final int m = (l + r) / 2;
if (pairDistancesNoGreaterThan(nums, m) >= k)
r = m;
else
l = m + 1;
}

return l;
}

private int pairDistancesNoGreaterThan(int[] nums, int m) {
int count = 0;
int j = 1;
// for each index i, find the first index j s.t. nums[j] > nums[i] + m,
// so pairDistancesNoGreaterThan for index i will be j - i - 1
for (int i = 0; i < nums.length; ++i) {
while (j < nums.length && nums[j] <= nums[i] + m)
++j;
count += j - i - 1;
}
return count;
}
}
``````

## Python

``````class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()

l = 0
r = nums[-1] - nums[0]

while l < r:
m = (l + r) // 2
count = 0

j = 0
for i in range(len(nums)):
while j < len(nums) and nums[j] <= nums[i] + m:
j += 1
count += j - i - 1

if count < k:
l = m + 1
else:
r = m

return l
``````