Smallest Range Covering K Lists

Problem

Given k sorted lists, return the smallest range [start, end] containing at least one element from every list; on ties choose the smaller start.

A heap holds the current element of each list along with the running maximum. Pop the smallest, record the range, push the next element from that list, and stop when a list is exhausted.

Hint

Advancing the list that owns the current minimum is the only move that can shrink the range.

Test cases

case 1

in: [[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]]

expected: [20,24]

case 2

in: [[[1,2,3],[1,2,3],[1,2,3]]]

expected: [1,1]

case 3

in: [[[10],[11]]]

expected: [10,11]

case 4

in: [[[1]]]

expected: [1,1]

case 5

in: [[[2,3],[1,4],[5,6]]]

expected: [3,5]

Starter codePython

def smallest_range(nums_lists):
    # Your code here
    pass

5 test cases · run your code against them in the editor