Skip to main content

Smallest Range Covering Elements from K Lists

Question​

Given 'K' lists of sorted integers, find the smallest range that includes at least one element from each of the 'K' lists.

Example 1
Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]

Solution​

all//Smallest Range Covering Elements from K Lists.py


def smallestRangeCoveringElementsFromKLists(lists):
    starts = [row[0] for row in lists]
    ends = [row[-1] for row in lists]
    min_range_start = min(starts)
    max_range_end = max(ends)
    min_range = (min_range_start, max_range_end)
    range_covered = False
    while not range_covered:
        range_covered = True
        for i in range(len(lists)):
            if min_range[0] > lists[i][0] or min_range[1] < lists[i][-1]:
                range_covered = False
                if min_range[0] > lists[i][0]:
                    min_range = (lists[i][0], min_range[1])
                else:
                    min_range = (min_range[0], lists[i][-1])
    return min_range