Minos Park

writing | projects | photos | drawings | code | lists | cs184 | ocf


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.

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

Tags: coding challenges draft