0719. Find K-th Smallest Pair Distance

https://leetcode.com/problems/find-k-th-smallest-pair-distance

Description

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

ac

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        // edge cases

        // find min and max
        Arrays.sort(nums);
        int n = nums.length;
        int r = nums[n-1] - nums[0], l = r;
        for (int i = 1; i < n; i++) {
            l = Math.min(l, nums[i] - nums[i-1]);
        }

        // binary search
        while (l < r) {
            int mid = l +  (r - l) / 2;
            int cnt = countPairs(nums, mid);
            if (cnt < k) l = mid + 1;
            else r = mid;
        }

        return l;
    }

    // how many pairs <= distance
    private int countPairs(int[] nums, int distance) {
        int res = 0, l = 0;
        for (int r = 1; r < nums.length; r++) {
            while (nums[r] - nums[l] > distance) {
                l++;
            }
            res += r - l;
        }
        return res;
    }
}
/*
find max/min distance(sort) -> binary search, use sliding window to count pairs
*/