# Python, Straightforward with Explanation

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

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

• @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``````

• Really smart solution!

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