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) while True: lbound, i = heap 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))
@robturtle Thank you, very straightforward explanation and easy to understand, I like this heap solution.