719. Find K Th Smallest Pair Distance¶

LeetCode Problem View on GitHub

719. Find K-th Smallest Pair Distance

Hard

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

Solution¶

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int low = 0, high = nums[n - 1] - nums[0], ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (count(mid, nums) < k) 
                low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
    private int count(int target, int arr[]) {
        int n = arr.length;
        int count = 0, j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && arr[j] - arr[i] <= target) 
                j++;
            count += j - i - 1; 
        }
        return count;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here