 Minos Park

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