# "1-liner" and "almost O(n)"

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.