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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Range Covering Elements from K Lists

Difficulty: Hard

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.

Key Insights

  • The solution involves tracking the minimum and maximum values within the current range that includes elements from all lists.
  • A min-heap (priority queue) can efficiently help in retrieving the smallest element across the k lists.
  • Using a max variable to keep track of the largest element currently in the range helps in determining when to move the range bounds.
  • The algorithm should iterate through the elements while adjusting the range to ensure it remains valid (i.e., covering 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 and k is the number of lists. Each insertion and extraction from the heap takes O(log k) time.

Space Complexity: O(k), for storing the heap and other variables.

Solution

The algorithm uses a min-heap to track the smallest current number from each of the k lists. We also maintain a variable for the maximum number seen so far. At each step, we check the current range defined by the smallest and largest numbers and update the best range found. We continue this process until we can no longer include a number from all lists.

Code Solutions

import heapq

def smallestRange(nums):
    min_heap = []
    current_max = float('-inf')
    best_range = [float('-inf'), float('inf')]

    # Initialize the heap with the first element of each list
    for i in range(len(nums)):
        heapq.heappush(min_heap, (nums[i][0], i, 0))
        current_max = max(current_max, nums[i][0])

    while min_heap:
        current_min, list_index, element_index = heapq.heappop(min_heap)

        # Update the best range if the current range is smaller
        if current_max - current_min < best_range[1] - best_range[0]:
            best_range = [current_min, current_max]

        # If we have reached the end of one of the lists, break
        if element_index + 1 == len(nums[list_index]):
            break

        # Push the next element from the same list to the heap
        next_value = nums[list_index][element_index + 1]
        heapq.heappush(min_heap, (next_value, list_index, element_index + 1))
        current_max = max(current_max, next_value)

    return best_range
← Back to All Questions