# Python AC solution by combining merge k sorted lists and minimum window substring

• This solution first uses merge k sorted lists to merge all the lists to one list, then applies minimum window substring to perform a linear scan to obtain the smallest range.

``````from heapq import *
class Solution(object):
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
# first, merge all the lists in sorted order
k = len(nums)

idx = [0 for _ in range(k)]
hq = [(l[0],i) for i,l in enumerate(nums) if l]
heapify(hq)

merged = [] # to store where the element is from

while hq:
val, i = heappop(hq)
merged.append((val, i))
idx[i] += 1
if idx[i] < len(nums[i]): heappush(hq, (nums[i][idx[i]], i))

count = 0
table = collections.defaultdict(int)
start, end = 0, 0

res = [0, float('inf')]
while end < len(merged):
i = merged[end][1]
if table[i] == 0: count += 1
table[i] += 1
end += 1

while count >= k:
if res[1] - res[0] > merged[end-1][0] - merged[start][0]:
res = [merged[start][0], merged[end-1][0]]
i = merged[start][1]
if table[i] == 1: count -= 1
table[i] -= 1
start += 1

return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.