python smallest range from multiple lists

Question

I need to find the smallest range from a group of integer lists using at least one element from each list.

list1=[228, 240, 254, 301, 391]
list2=[212, 345, 395]
list3=[15, 84, 93, 103, 216, 398, 407, 488]

In this example the smallest range would be [391:398], because this covers the values 391, 395 and 398 from the three lists.

Each list will have at least one value and there could be many more lists

What would be the quickest computationally way to find the range?

Answer 1

Since your input lists are sorted, you can use a merge sort and you only need to test a range whenever the next value that is being merged in came from a different list than the last. Track the last value you've seen on each of the lists, and calculate ranges between the lowest value and the current. This is an O(N) linear time approach, where N is the total number of elements of all input lists.

The following implements that approach:

def smallest_range(*lists):
    iterables = [iter(it) for it in lists]
    iterable_map = {}
    for key, it in enumerate(iterables):
        try:
            iterable_map[key] = [next(it), key, it]
        except StopIteration:
            # empty list, won't be able to find a range
            return None
    lastvalues, lastkey = {}, None
    candidate, candidatediff = None, float('inf')

    while iterable_map:
        # get the next value in the merge sort
        value, key, it = min(iterable_map.values())
        lastvalues[key] = value

        if len(lastvalues) == len(lists) and lastkey != key:
            minv = min(lastvalues.values())
            difference = value - minv
            if candidatediff > difference:
                candidate, candidatediff = (minv, value), difference
        lastkey = key

        try:
            iterable_map[key][0] = next(it)
        except StopIteration:
            # this iterable is empty, remove it from consideration
            del iterable_map[key]

    return candidate

Demo:

>>> list1 = [228, 240, 254, 301, 391]
>>> list2 = [212, 345, 395]
>>> list3 = [15, 84, 93, 103, 216, 398, 407, 488]
>>> smallest_range(list1, list2, list3)
(391, 398)