632 Smalllest Range Covering Elements from K Lists

Problem Statement

You have k lists of sorted integers in non-decreasing order.

Instructions

• 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.

For the whole problem statement, please refer here.

Plans

• Find the smallest range that includes at least one number from each of the k lists of sorted integers.

• This approach will allow us to efficiently manage the current minimum and maximum values from the lists.

• Track the next element to be considered from each list.

• Continue to expand our range until all lists are represented.

• Update the smallest range whenever a new valid range is found.

Solution

import heapq
from typing import List

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # Initialize the min-heap
        min_heap = []
        current_max = float('-inf')  # It will track the maximum number in the current range
        
        # Populate the heap with the first element of each list
        for i in range(len(nums)):
            heapq.heappush(min_heap, (nums[i][0], i, 0))  # (value, list index, element index)
            current_max = max(current_max, nums[i][0])
            
        # Initialize the smallest range
        smallest_range = [float('-inf'), float('inf')]
        
        # While we can still form a valid range
        while min_heap:
            current_min, list_index, num_index = heapq.heappop(min_heap)
            
            # Update the smallest range if the current range is smaller
            if current_max - current_min < smallest_range[1] - smallest_range[0]:
                smallest_range = [current_min, current_max]
            
            # If there's a next element in the current list, push it to the heap
            if num_index + 1 < len(nums[list_index]):
                next_val = nums[list_index][num_index + 1]
                heapq.heappush(min_heap, (next_val, list_index, num_index + 1))
                current_max = max(current_max, next_val)
            else:
                # If we reach the end of any list, break out
                break
        
        return smallest_range

Explanation

1. Initialize

   • We start by creating a min_heap which will store tuples of the form (value, list_index, element_index). The value is the integer from the list, the list_index helps identify which list it came from, and the element_index indicates the position in that list.

   • The variable current_max is used to keep track of the maximum number in the current range.

2. Populate the Heap

   • Initially, we populate the heap with the first element of each list. We also update current_max as we insert elements.

3. Finding the Smallest Range

   • Continously extract the minimum element from the healp. This gives us the smallest current element (current_min).

   • At each step, we check if the range defined by current_min and current_max is the smallest we have found so far.

   • If is is smallest, we update our smallest_range.

4. Push Next Elements

   • After removing the smallest element, if there is a next element in the same list, we push that next element into the heap and update current_max if the new value is larger.

   • If we exhaust any list (no more elmements to pus), we stop the process as we can no longer form a valid range.

5. Return the Result

   • The method finally returns the smallest range that covers at least one element from each of the input lists.