k-list.py

#!/usr/bin/env python2
import sys

"""
You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
"""


class SortedList(object):
    def __init__(self, li):
        self.list = li
        self.length = len(li)
        
        # keep pointer to the current location
        self.index = 0
        
    def get_value(self):
        return self.list[self.index]
        
    def next(self):
        self.index += 1

        return self.index < self.length


class Location():
    def __init__(self, index_list, value):
        self.index_list = index_list
        self.value = value


def find_min_and_max(lists, lists_length):
    # check for empty input
    if not lists or not isinstance(lists, list):
        return
    
    #print "-" * 23
    
    # init min and maximum from current pointers
    min_location = Location(0, lists[0].get_value())
    max_location = Location(0, lists[0].get_value())
    
    for i in xrange(1, lists_length):
        li = lists[i]
        li_value = li.get_value()
        
        #print "value:", li_value
        
        # find minimum
        if li_value < min_location.value:
            min_location = Location(i, li_value)
            #print "min:", li_value
            
        # find maximum    
        if li_value > max_location.value:
            max_location = Location(i, li_value)
            #print "max:", li_value

    return min_location, max_location


def main():
    lists = [
        SortedList([4, 10, 15, 24, 26]),
        SortedList([0, 9, 12, 20]),
        SortedList([5, 18, 22, 30])
    ]
    lists_length = len(lists)
    
    smallest_range = sys.maxint
    smallest_min_location = smallest_max_location = None
    
    while True:
        min_location, max_location = find_min_and_max(lists, lists_length)
        found_range = max_location.value - min_location.value
        
        # found new smallest range
        if found_range < smallest_range:
            smallest_range = found_range
            smallest_min_location = min_location
            smallest_max_location = max_location
            
        # update minimum location
        if not lists[min_location.index_list].next():
            break
    
    print "Smallest range is %d and it's between [%d, %d]" % (smallest_range, smallest_min_location.value, smallest_max_location.value)


if __name__ == "__main__":
    main()