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.

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.

Example 1:

Note:

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

 

Let L = 1000000, N = nums.size().

The optimal solution is in O(N log L) time via binary search and linear scanning.

Solution Find K-th Smallest Pair Distance

Convert the problem into: given X, how many pairs of numbers are greater or equals to X.

This can be done in O(N), then search X in log(L)

C++

Python