I reduce the problem to the old Kth Smallest Element in a Sorted Matrix problem. Explanation below the code.

#### Ruby "1-liner" (as in, I just wrote one new line):

```
def smallest_distance_pair(nums, k)
kth_smallest(nums.sort!.map { |x| -> j { x - nums[~j] } }, k + (1..nums.size).sum)
end
# copy&paste old solution from https://discuss.leetcode.com/topic/52936/o-n-log-n-ruby-solution
def kth_smallest(matrix, k)
...
```

#### Python ~~O(n)~~ Edit: O(n log n)

```
def smallestDistancePair(self, nums, k):
nums.sort()
class Row(int):
def __getitem__(self, j):
return self - nums[~j]
n = len(nums)
return self.kthSmallest(map(Row, nums), k + n*(n+1)/2)
# copy&paste old solution from https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows
def kthSmallest(self, matrix, k):
...
```

Edit: Darn, I originally thought it's O(n), but I just realized that I forgot that I'm sorting the list. Everything else is only O(n), but that sorting makes it only O(n log n). Then again, it's the built-in sort function, so that's a very fast O(n log n). Probably faster than the O(n) of the rest of the code.

#### Explanation

I sort the input and then build a virtual sorted matrix of (non-absolute) differences, for example for [2, 4, 5, 9]:

```
| 9 5 4 2
--+------------
2 | -7 -3 -2 0
4 | -5 -1 0 2
5 | -4 0 1 3
9 | 0 4 5 7
```

The antidiagonal of zeros is from non-pairs (elements paired with themself) and the upper left triangle of negative numbers are "wrong-order" pairs. None of these interest us, so I increase the given `k`

by how many of these there are (i.e., by sum(1..n) = n(n+1)/2)).

Of course I'm not explicitly building that matrix. It can be 10000×10000 large. Ain't Nobody Got Time for That (or Memory). I'm just building a *virtual* matrix. Each row is not an explicit array but just an object that allows access by index and computes the accessed values on-the-fly.