Python, Heap-based solution

  • 16
    def smallestRange(self, A):
        pq = [(row[0], i, 0) for i, row in enumerate(A)]
        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

  • 0

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

  • 0

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

  • 0

    Such elegant code. Thank you!

  • 0

    @awice Thanks for explanation.

  • 0

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

Log in to reply

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