> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0719-find-k-th-smallest-pair-distance.md).

# 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

```java
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
*/
```