##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/719.html

# 719. Find K-th Smallest Pair Distance (Hard)

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

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.


Note:

1. 2 <= len(nums) <= 10000.
2. 0 <= nums[i] < 1000000.
3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

Related Topics:
Array, Binary Search, Heap

Similar Questions:

// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Time: O(NlogN + NlogNlogD) where D is the distance between the minimal distance and the maximal distance.
// Space: O(1)
class Solution {
int count(vector<int> &A, int M) {
int cnt = 0;
for (int i = 0; i < A.size(); ++i) cnt += upper_bound(begin(A), end(A), A[i] + M) - begin(A) - i - 1;
return cnt;
}
public:
int smallestDistancePair(vector<int>& A, int k) {
sort(begin(A), end(A));
int L = INT_MAX, R = A.back() - A[0];
for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]);
while (L <= R) {
int M = (L + R) / 2, cnt = count(A, M);
if (cnt < k) L = M + 1;
else R = M - 1;
}
return L;
}
};


## Solution 2.

We can reduce the time complexity of count function from O(NlogN) to O(N).

// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Time: O(NlogN + NlogD) where D is the distance between the minimal distance and the maximal distance.
// Space: O(1)
class Solution {
int count(vector<int> &A, int M) {
int cnt = 0, i = 0, j = 0, N = A.size();
while (i < N) {
while (j < N && A[j] - A[i] <= M) ++j;
cnt += j - i - 1;
++i;
}
return cnt;
}
public:
int smallestDistancePair(vector<int>& A, int k) {
sort(begin(A), end(A));
int L = INT_MAX, R = A.back() - A[0];
for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]);
while (L <= R) {
int M = (L + R) / 2, cnt = count(A, M);
if (cnt < k) L = M + 1;
else R = M - 1;
}
return L;
}
};

• class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int length = nums.length;
int low = 0, high = nums[length - 1] - nums[0];
while (low < high) {
int mid = (high - low) / 2 + low;
int count = 0, left = 0;
for (int right = 0; right < length; right++) {
while (nums[right] - nums[left] > mid)
left++;
count += right - left;
}
if (count >= k)
high = mid;
else
low = mid + 1;
}
return low;
}
}

############

class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0];
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid, nums) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

private int count(int dist, int[] nums) {
int cnt = 0;
for (int i = 0; i < nums.length; ++i) {
int left = 0, right = i;
while (left < right) {
int mid = (left + right) >> 1;
int target = nums[i] - dist;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
cnt += i - left;
}
return cnt;
}
}

• // OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Time: O(NlogN + NlogNlogD) where D is the distance between the minimal distance and the maximal distance.
// Space: O(1)
class Solution {
int count(vector<int> &A, int M) {
int cnt = 0;
for (int i = 0; i < A.size(); ++i) cnt += upper_bound(begin(A), end(A), A[i] + M) - begin(A) - i - 1;
return cnt;
}
public:
int smallestDistancePair(vector<int>& A, int k) {
sort(begin(A), end(A));
int L = INT_MAX, R = A.back() - A[0];
for (int i = 1; i < A.size(); ++i) L = min(L, A[i] - A[i - 1]);
while (L <= R) {
int M = (L + R) / 2, cnt = count(A, M);
if (cnt < k) L = M + 1;
else R = M - 1;
}
return L;
}
};

• class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(dist):
cnt = 0
for i, b in enumerate(nums):
a = b - dist
j = bisect_left(nums, a, 0, i)
cnt += i - j
return cnt

nums.sort()
return bisect_left(range(nums[-1] - nums[0]), k, key=count)


• func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
left, right := 0, nums[n-1]-nums[0]
count := func(dist int) int {
cnt := 0
for i, v := range nums {
target := v - dist
left, right := 0, i
for left < right {
mid := (left + right) >> 1
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
cnt += i - left
}
return cnt
}
for left < right {
mid := (left + right) >> 1
if count(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}

• function smallestDistancePair(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let left = 0,
right = nums[n - 1] - nums[0];
while (left < right) {
let mid = (left + right) >> 1;
let count = 0,
i = 0;
for (let j = 0; j < n; j++) {
// 索引[i, j]距离nums[j]的距离<=mid
while (nums[j] - nums[i] > mid) {
i++;
}
count += j - i;
}
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}