# Week 3 Session 1 Walkthrough: Smallest Range Covering Elements from K Lists

[Original Question](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/)

## Solution

def smallest_range(nums):
    # store the first element in each list in a min heap
    # we need to store the number, corresponding row for that number, and index in row for that number
    heap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(heap) # this creates the heap
    
    # Best interval so far with the minimum set to negative infinity and the maximum set to positive infinity
    best_interval = (float("-inf"), float("inf")) 
    
    # go through all the rows to get the current highest number
    curr_max = max(row[0] for row in nums) 

    while heap:
        # removes the next smallest element from the heap
        curr_min, row_num, row_index = heapq.heappop(heap) 
        
        if curr_max - curr_min < best_interval[1] - best_interval[0]:
            best_interval = (curr_min, curr_max)

        if row_index + 1 == len(nums[row_num]):
            return best_interval

        new_elem = nums[row_num][row_index+1]
        curr_max = max(curr_max, new_elem)
        heapq.heappush(heap, (new_elem, row_num, row_index+1))