## Find k-th Smallest Pair Distance

####
*This is a draft post.*

*January 2021*

**Problem #719, LeetCode**

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:

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

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

Accepted 40.3K Submissions 124.1K

**Solution**

Naive approach would be to go through the `len(nums) * (len(nums) - 1) / 2`

pairs and put them in a priority queue. For the output, index the appropriate `k`

and return the value.

- Complexity analysis on the naive solution

Now, over to a bit more clever ways to achieve this.. initial thought was to have the `nums`

array sorted. Then, one can select `k`

th pair from the beginning. However, this does not work as the smallest absolute distance does not relate to the magnitude of the array values itself.

```
counter example:
Input:
nums = [0,2,4,10000,10001,10003,20000]
k = 1
Output: 1
```

- Clever solution - I sense there maybe one

*Tags:
coding challenges
draft
*