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 - ans: 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.
@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.
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 - ans: ans = left, right return ans
@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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.