Python heap solution with explanation


  • 1
    R

    Suppose we have formed a range with one element from each list. We can form another range by advancing one value along its belonging list. If we're not advancing the smallest value, the left bound will remain unchanged and the right bound will be increased. It's impossible to find the smallest range within such searching space. In other words, it's safe to advancing the smallest value in the current range.

    def smallestRange(self, nums):
        iters = [iter(l) for l in nums]
        heap = [(next(it), i) for i,it in enumerate(iters)]
        heapq.heapify(heap)
    
        lo, hi = 0, float('inf')
        rbound = max(heap)[0]
        while True:
            lbound, i = heap[0]
            if rbound - lbound < hi - lo:
                lo, hi = lbound, rbound
            nxt = next(iters[i], None)
            if nxt is None:
                return [lo, hi]
            rbound = max(rbound, nxt)
            heapq.heappushpop(heap, (nxt,i))
    

  • 0
    A

    @robturtle Thank you, very straightforward explanation and easy to understand, I like this heap solution.


Log in to reply
 

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