Problem statement

https://binarysearch.com/problems/Smallest-Difference/

Solution

Equal to Leetcode 0632 Smallest Range Covering Elements from K Lists.

Complexity

Time complexity is O(n log m), space complexity is O(m).

Code

class Solution:
    def solve(self, nums):
        nums = [sorted(x) for x in nums]
        heap = [(i[0], j, 0) for j, i in enumerate(nums)]
        cur_max = max(heap)[0]
        heapify(heap)
        ans = (-float("inf"), float("inf"))
        
        while True:
            ans = min(ans, (heap[0][0], cur_max), key = lambda x: x[1] - x[0])
            num, num_list, ind = heappop(heap)
            if ind == len(nums[num_list]) - 1: break
            heappush(heap, (nums[num_list][ind+1], num_list,ind+1) )
            cur_max = max(cur_max, nums[num_list][ind+1])
        
        return ans[1] - ans[0]