719

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:

• Find K Pairs with Smallest Sums (Medium)
• Kth Smallest Element in a Sorted Matrix (Medium)
• Find K Closest Elements (Medium)
• Kth Smallest Number in Multiplication Table (Hard)
• K-th Smallest Prime Fraction (Hard)

Solution 1. Binary Answer

// OJ: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};