# Python, Heap-based solution

• ``````def smallestRange(self, A):
pq = [(row[0], i, 0) for i, row in enumerate(A)]
heapq.heapify(pq)

ans = -1e9, 1e9
right = max(row[0] for row in A)
while pq:
left, i, j = heapq.heappop(pq)
if right - left < ans[1] - ans[0]:
ans = left, right
if j + 1 == len(A[i]):
return ans
v = A[i][j+1]
right = max(right, v)
heapq.heappush(pq, (v, i, j+1))
``````

Keep a heap of the smallest elements. As we pop element A[i][j], we'll replace it with A[i][j+1]. For each such element `left`, we want `right`, the maximum of the closest value in each row of the array that is `>= left`, which is also equal to the current maximum of our heap. We'll keep track of `right` as we proceed.

Edited with thanks to @StefanPochmann

• I don't think the first line `map(heapq.heapify, A)` and the last line `return ans` are necessary. Are they?

• @StefanPochmann
It's not - just need to iterate over all the elements in order

• Such elegant code. Thank you!

• @awice Thanks for explanation.

• amazing solution! I wish i could upvote it more than once :)

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