Smallest Range Covering Elements from K Lists

February 4, 2024

Problem Statement #

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. Your algorithm’s complexity must be better than brute force, meaning you can’t just check every possible range.

Solution Approach #

The solution involves using a min-heap to keep track of the minimum value across the k lists and expanding the range until it covers at least one number from each list. The heap is used to efficiently find the minimum element and its corresponding list among the k lists.

Algorithm Steps #

1. Initialize a min-heap to store elements in the form (value, listIndex, elementIndex) where value is the element value, listIndex is the index of the list the element belongs to, and elementIndex is the index of the element in its list.
2. Add the first element of each list to the heap.
3. Keep track of the current range and the smallest range found so far.
4. Pop elements from the heap (this gives the current minimum element). Each time you pop an element, add the next element from the same list to the heap.
5. Update the current range every time the heap is updated.
6. If the current range covers at least one number from each list (checked by ensuring the heap always contains elements from all k lists), and if the current range is smaller than the smallest found so far, update the smallest range.
7. Continue until one of the lists is exhausted, indicating you cannot cover all k lists with any larger ranges.
8. Return the smallest range found.

Code (Python) #

import heapq

def smallestRange(nums):
    minHeap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(minHeap)

    right = max(row[0] for row in nums)
    ans = float("-inf"), float("inf")

    while minHeap:
        left, i, j = heapq.heappop(minHeap)
        if right - left < ans[1] - ans[0]:
            ans = left, right
        if j + 1 == len(nums[i]):
            return ans
        v = nums[i][j+1]
        right = max(right, v)
        heapq.heappush(minHeap, (v, i, j+1))

    return ans

# Example usage
nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
print(smallestRange(nums))  # Output: (20, 24)

Time Complexity #

O(N log k), where N is the total number of elements across all k lists, and k is the number of lists. The log k term is due to operations on the heap.

Space Complexity #

O(k), for the heap, where k is the number of lists.