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

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 kth 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