def smallestRange(self, A): pq = [(row, i, 0) for i, row in enumerate(A)] heapq.heapify(pq) ans = -1e9, 1e9 right = max(row for row in A) while pq: left, i, j = heapq.heappop(pq) if right - left < ans - ans: 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?
It's not - just need to iterate over all the elements in order
@awice Thanks for explanation.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.