Python, Straightforward with Explanation


  • 2
    def smallestRange(self, A):
        A = [row[::-1] for row in A]
        
        ans = -1e9, 1e9
        for left in sorted(reduce(set.union, map(set, A))):
            right = -1e9
            for B in A:
                while B and B[-1] < left:
                    B.pop()
                if not B:
                    return ans
                right = max(right, B[-1])
            if right - left < ans[1] - ans[0]:
                ans = left, right
        return ans
    

    Clearly, each left and right bound must be a value in some array.

    For each candidate left bound equal to some value in some array, let's determine the next-rightmost value of each array. If it doesn't exist, then our left is already too large for any subsequent candidates to have a solution. Otherwise, we can choose the maximum of these to be the corresponding right bound for our candidate left bound. We take the maximum of all such candidates.


  • 0
    R

    @awice Let n be the length of each array, in the worst case it will only pop one element for each outer for iteration. That makes it O(nk^2), which is worse than the priority queue solution.


  • 2

    @awice
    Really nice solution. I upvoted. A little improvement:
    A = [row[::-1] for row in A] takes a lot of time and it is not necessary.
    The following solution improve the original one, from 450ms to 250ms.

    def smallestRange(self, A):
            ans = -1e9, 1e9
            for right in sorted(set(x for l in A for x in l))[::-1]:
                for B in A:
                    while B and right < B[-1]:
                        B.pop()
                    if not B:
                        return ans
                left = min(B[-1] for B in A)
                if right - left <= ans[1] - ans[0]:
                    ans = left, right
            return ans

  • 0

    Really smart solution!


  • 0

    @robturtle I don't think it's O(nk^2). If all elements are equal, then it's O(kn^2). Thus, it's a brutal force solution but the implementation is better than other implementations.


Log in to reply
 

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