< Back





632. Smallest Range Covering Elements from K Lists

We're given k lists of increasing integers. We need to define a range from [start, end] where at
least 1 element from each of the k lists is present. The range also need to be as small as possible.
Smallness is defined as, for [a, b] and [c, d], b - a < d - c or b - a = d - c and a < c.

We essentially solve this with a combination of sliding window and a min heap. To kick off our
sliding window implementation, we'll maintain start and end variables for tracking the current
smallest range. We'll also maintain a maximum variable to track the maximum value we've seen so far.
This maximum value will allow us to shrink the range as we process new values in each loop.

We proceed to start with the 0th element in each array, pushing them onto a heap. Each time we pop
from the heap, we'll receive the smallest element that needs to be evaluated, so far. We also store
the current index correlating to this element with its lists in the k lists provided, as well as the
index of the list we're currently evaluating. This allows us to detect when we've hit the end of a
list in our k lists, as well as select the next element in the k lists to push to the heap.

While the heap exists, we pop, receiving the smallest integer across all the lists. If this minimum
value less the current maximum is less than the current range, we update the range. If we've reached
the end of this list, we return the range. Otherwise, we find the first element smaller than this one
in the current list and push it to the heap. We also update the maximum value if the new element is
greater than the current maximum.

The solution is as follows:


  from heapq import heappush, heappop

  class Solution:
      def smallestRange(self, nums: List[List[int]]) -> List[int]:
          heap, start, end, maximum = [], float("-inf"), float("inf"), float("-inf")

          for i, arr in enumerate(nums):
              heappush(heap, (arr[0], 0, i))
              maximum = max(maximum, arr[0])

          while heap:
              minimum, i, arr_index = heappop(heap)

              if maximum - minimum < end - start:
                  start, end = minimum, maximum

              n = len(nums[arr_index])

              if i == n - 1:
                  return [start, end]

              while i < n:
                  if nums[arr_index][i] > minimum or i == n - 1:
                      heappush(heap, (nums[arr_index][i], i, arr_index))
                      maximum = max(maximum, nums[arr_index][i])
                      break

                  i += 1


_ Time Complexity:

  O(n * log(m)) - Where m is the number of lists and n is the number of elements in the lists. 

_ Space Complexity:

  O(m) - At most, we'll have m elements in our heap, where m is the number of lists.