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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0719-find-k-th-smallest-pair-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.