Leetcode Daily Question 13/10/2024 - 632. Smallest Range Covering Elements from K Lists

Problem Description:

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists. | -------------------------------------------- | We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

from typing import List
import heapq
class Solution:
  def smallestRange(self, nums: List[List[int]]) -> List[int]:
    min_heap = []
    heapq.heapify(min_heap)
    max_val = float('-inf')
    for i, num in enumerate(nums):
      heapq.heappush(min_heap, (num[0], i, 0))
      max_val = max(max_val, num[0])
      
    min_range = [float('-inf'), float('inf')]
    
    while min_heap:
      min_val, arr_index, elt_index = heapq.heappop(min_heap)
      
      if max_val - min_val < min_range[1] - min_range[0] or \
      max_val - min_val == min_range[1] - min_range[0] and \
      min_val < min_range[0]:
        min_range = [min_val, max_val]
        
      if elt_index + 1 < len(nums[arr_index]):
        heapq.heappush(min_heap, (nums[arr_index][elt_index + 1], arr_index, elt_index + 1))
        max_val = max(max_val, nums[arr_index][elt_index + 1])
      else:
        break
      
    return min_range

Explanation:

We can solve this problem using a sweep line approach with a min-heap to keep track of the current min/max elements from nums.

We initialise the heap by pushing the smallest element from each list into it. We also keep track of the largest element among these initial values. This allows us to define the current range as the interval between the smallest (from the heap) and the largest (tracked separately) elements.

In each step, we pop the smallest element from the heap and compare the current range, defined by the smallest and largest elements, with the smallest range we have seen so far. If the current range is smaller, we update our result.

After popping the smallest element, we push the next element from the same list into the heap to maintain at least one element from each list in the heap. If this new element is larger than the current maximum, we update the maximum value as well.

We repeat this process until one of the lists runs out of elements. At that point, we can no longer form a valid range that includes at least one element from each list, so the process stops.

Let's elucidate the approach with an example:

Consider nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]].
We start with min heap, min_heap = [], pushing the smallest element from each array along with the array index, and 
element position index in the heap.
min_heap = [(0,1,0), (4,0,0), (5,2,0)]
We also keep track of the maximum value seen, in this case max_val = 5
Now we pop the top element from the heap to compare this range with the range we have seen.
Since we have not seen any, our min range equals [0,5].
We push a new element from the array we popped from, so max_val = 9 and min_heap = [(4,0,0),(5,2,0),(9,1,1)].
Next, we pop (4,0,0), since this range is not smaller than min range, we do not update the range.
We push a new element from array 1, so max_val = 10 min_heap = [(5,2,0),(9,1,1),(10,0,1)].
pop (5,2,0) -> range does not change -> max_val = 19 min_heap = [(9,1,1),(10,0,1),(18,2,1)].
Continuing like this, we find that min range equals [20, 24].

Let's build our code carefully. First we construct the min heap and push the smallest element form each array into it, while also tracking the max value encountered

min_heap = []
heapq.heapify(min_heap)
max_val = float('-inf')

for i, num in enumerate(nums):
  heapq.heappush(min_heap, (num[0], i, 0))
  max_val = max(max_val, num[0])

Then we define an auxilary min range and do our iteration.

min_range = [float('-inf'), float('inf')]

while min_heap:
  min_val, arr_index, elt_index = heapq.heappop(min_heap)
  
  if max_val - min_val < min_range[1] - min_range[0] or \
  max_val - min_val == min_range[1] - min_range[0] and \
  min_val < min_range[0]:
    min_range = [min_val, max_val]
  
  if elt_index + 1 < len(nums[arr_index]): # Check if we can push any more element from the popped element's arr.
    heapq.heappush(min_heap, (nums[arr_index][elt_index + 1], arr_index, elt_index + 1))
    max_val = max(max_val, nums[arr_index][elt_index + 1])
  else: # When any one of the array runs out of elements to push.
  	break

return min_range

The time complexity is O(n log k), where k is the number of arrays in nums and n is the length of the smallest array in nums. Heap operations take O(log k) time. Since we need to iterate until at least one array runs out of elements, this will take O(n log k) time.

The space complexity is O(k). Since we store exactly one element from each array at any one point in time.

The full solution can be found near the top of the page.