We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Range Covering Elements from K Lists

Number: 632

Difficulty: Hard

Paid? No

Companies: Amazon, PhonePe, Google, Meta, Microsoft, Flipkart, Snap, Apple, Lyft

Problem Description

Given k sorted lists, find the smallest range [a, b] such that at least one number from each list falls in the range. The range is considered smaller if (b - a) is smaller, or if equal, the lower a is prioritized.

Key Insights

  • Use a min heap to maintain the smallest current element among the selected elements from each list.
  • Track the current maximum among the chosen elements to easily compute the range.
  • Iteratively replace the minimum element with the next element from the same list and update the current maximum.
  • Stop when one of the lists is exhausted, as the range must include at least one element from each list.

Space and Time Complexity

Time Complexity: O(N log k), where N is the total number of elements across all lists. Space Complexity: O(k) for the heap, plus additional space for storing the range.

Solution

The solution uses a min heap (priority queue) that stores a tuple containing the current element, the index of the list it comes from, and its index in that list. Initially, the first element from each list is inserted into the heap and the current maximum among them is tracked. In each iteration, the smallest element is removed (heap root) which provides the current minimum, and the range [current_min, current_max] is assessed. If the list from which the minimum element was extracted has a next element, that element is inserted into the heap and the current maximum is updated if necessary. This process continues until one of the lists is exhausted.

Code Solutions

import heapq

def smallestRange(nums):
    # Initialize the min-heap and current maximum value
    heap = []
    current_max = float('-inf')
    
    # Add the first element of each list to the heap
    for i, lst in enumerate(nums):
        value = lst[0]
        heapq.heappush(heap, (value, i, 0))
        current_max = max(current_max, value)
    
    best_range = [float('-inf'), float('inf')]
    
    # Process until one list is exhausted
    while heap:
        current_min, list_idx, elem_idx = heapq.heappop(heap)
        
        # Update the best range if the current range is smaller
        if current_max - current_min < best_range[1] - best_range[0] or \
           (current_max - current_min == best_range[1] - best_range[0] and current_min < best_range[0]):
            best_range = [current_min, current_max]
        
        # If there is no next element in the same list, break out
        if elem_idx + 1 == len(nums[list_idx]):
            break
        next_value = nums[list_idx][elem_idx + 1]
        heapq.heappush(heap, (next_value, list_idx, elem_idx + 1))
        current_max = max(current_max, next_value)
    
    return best_range

# Example Usage:
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
print(smallestRange(nums))
← Back to All Questions