You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists. 

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].




Note:

The given list may contain duplicates, so ascending order means >= here.
1 k 
 -105 value of elements 5.
For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

Difficulty: interview

Starter code:

class Solution:
    def smallestRangeI(self, A: List[int], K: int) -> int:


Solutions:
from functools import reduce
 class Solution:
     def smallestRange(self, nums):
         """
         :type nums: List[List[int]]
         :rtype: List[int]
         """
         k = len(nums)
         idx = [0]*k
         
         dic = collections.defaultdict(list)
         
         for i in range(k):
             dic[nums[i][0]].append(i)
         
         mi, ma = min(dic.keys()), max(dic.keys())
         
         ret = (mi, ma)
         while True:
             for i in dic[mi]:
                 idx[i] += 1
                 if idx[i]==len(nums[i]):
                     return ret
                 dic[nums[i][idx[i]]].append(i)
             dic.pop(mi)
             mi, ma = min(dic.keys()), max(dic.keys())
             if ma-mi<ret[1]-ret[0]:
                 ret = (mi, ma)