Leetcode 632 Solution

This article provides solution to leetcode question 632 (smallest-range-covering-elements-from-k-lists)
Categories:
Tags:
Access this page by simply typing in "lcs 632" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists

Solution

class Solution:
    def smallestRange(self, nums_list: List[List[int]]) -> List[int]:
        heap = []
        max_in_heap = 0

        for nums in nums_list:
            heapq.heappush(heap, (nums[0], 1, nums))
            max_in_heap = max(nums[0], max_in_heap)

        ans = None
        while heap:
            num, i, nums = heapq.heappop(heap)
            if ans is None or ans[1] - ans[0] > max_in_heap - num:
                ans = (num, max_in_heap)

            if i == len(nums):
                break

            max_in_heap = max(max_in_heap, nums[i])
            heapq.heappush(heap, (nums[i], i + 1, nums))

        return ans