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


  • 4

    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.


Log in to reply
 

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