python O(N * log(K)) heap + FIFO queue


  • 0
    X
    class Solution(object):
        def smallestRange(self, nums):
            """
            :type nums: List[List[int]]
            :rtype: List[int]
            """
            tot = sum(map(len, nums))
            from heapq import merge
            from collections import deque
            arrs = [ [(v, i) for v in arr] for i, arr in enumerate(nums) ]
            pq = merge(*arrs)
            sortedq = deque([])
            cnts = [0] * len(nums)
            seen = 0
            minr = float('inf'), float('inf')
            for _ in range(tot):
                v, i = next(pq)
                sortedq.append((v, i))
                if cnts[i] == 0:
                    seen += 1            
                cnts[i] += 1
                while cnts[sortedq[0][1]] > 1:
                    cnts[sortedq[0][1]] -= 1
                    sortedq.popleft()
                if seen >= len(nums):
                    minr = min(minr, ((sortedq[-1][0] - sortedq[0][0]), sortedq[0][0]))
            return [minr[1], minr[1] + minr[0]]
    
    

Log in to reply
 

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