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:

Solution 1. Binary Answer

// 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;
    }
    
    

All Problems

All Solutions