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


  • 0
    S

    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
    

Log in to reply
 

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