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

# 719. Find K-th Smallest Pair Distance

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:**<br>

```
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:**<br>

1. `2 <= len(nums) <= 10000`.
2. `0 <= nums[i] < 1000000`.
3. `1 <= k <= len(nums) * (len(nums) - 1) / 2`.

```cpp
// Sort + Binary Search
int smallestDistancePair(vector<int>& nums, int k) { // time: O(nlogn + n^2 * log(max - min)); space: O(1)
    sort(nums.begin(), nums.end());
    int l = 0, r = nums.back() - nums.front(), n = nums.size();
    while (l < r) {
        int mid = l + (r - l) / 2, cnt = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && nums[j] - nums[i] <= mid) ++j;
            cnt += (j - i - 1);
        }
        if (cnt < k) l = mid + 1;
        else r = mid;
    }
    return r;
}
```