Problem

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.

Examples

Example 1:

**Input:** nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
**Output:** [20,24]
**Explanation:** 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

**Input:** nums = [[1,2,3],[1,2,3],[1,2,3]]
**Output:** [1,1]

Solution

Method 1 - Using Heap

The goal is to find the smallest range [a, b] that includes at least one number from each of the k sorted lists. The smallest range is defined by the difference b - a and, in case of a tie, by the smallest starting point a.

Here is the approach:

  1. Priority Queue Initialization: Use a min-heap to keep track of the smallest elements from each list. The heap will store tuples of the form (value, row, index), where value is the element from the list, row is the index of the list, and index is the index within the list.
  2. Initialize Heap with First Elements:
    • Push the first element from each list into the min-heap.
    • Keep track of the maximum value among the first elements using a variable max_value.
  3. Finding the Range:
    • The initial range is determined by the minimum and maximum values in the heap.
    • Iterate by removing the smallest element from the heap and pushing the next element from the same list into the heap. Update the range if the new range formed by the new minimum and the current maximum is smaller.
    • Continue this process until one of the lists is exhausted.
  4. Update the Range:
    • Keep track of the smallest range found so far by comparing the new range formed after each insertion into the heap.

Code

Java
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // PriorityQueue to simulate a min-heap
        PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
        
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int value = nums.get(i).get(0);
            minHeap.offer(new Element(value, i, 0));
            maxValue = Math.max(maxValue, value);
        }
        
        int rangeStart = 0;
        int rangeEnd = Integer.MAX_VALUE;
        
        while (minHeap.size() == nums.size()) {
            Element curr = minHeap.poll();
            
            if (maxValue - curr.value < rangeEnd - rangeStart || 
                (maxValue - curr.value == rangeEnd - rangeStart && curr.value < rangeStart)) {
                rangeStart = curr.value;
                rangeEnd = maxValue;
            }
            
            if (curr.index + 1 < nums.get(curr.row).size()) {
                int nextValue = nums.get(curr.row).get(curr.index + 1);
                minHeap.offer(new Element(nextValue, curr.row, curr.index + 1));
                maxValue = Math.max(maxValue, nextValue);
            }
        }
        
        return new int[]{rangeStart, rangeEnd};
    }
    
    // Helper class to store elements in the min-heap
    class Element {
        int value;
        int row;
        int index;
        
        Element(int value, int row, int index) {
            this.value = value;
            this.row = row;
            this.index = index;
        }
    }

}
Python
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # Initialize the heap
        min_heap = []
        max_value = float('-inf')
        
        # Insert first element of each list into the heap
        for row in range(len(nums)):
            value = nums[row][0]
            heapq.heappush(min_heap, (value, row, 0))
            max_value = max(max_value, value)
        
        result = [float('-inf'), float('inf')]
        
        while len(min_heap) == len(nums):
            min_value, row, idx = heapq.heappop(min_heap)
            
            # Update the result if a smaller range is found
            if max_value - min_value < result[1] - result[0] or (max_value - min_value == result[1] - result[0] and min_value < result[0]):
                result = [min_value, max_value]
            
            # If there are remaining elements in the current list, push the next element into the heap
            if idx + 1 < len(nums[row]):
                next_value = nums[row][idx + 1]
                heapq.heappush(min_heap, (next_value, row, idx + 1))
                max_value = max(max_value, next_value)
        
        return result

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 operation on the heap takes O(log k) time.
  • 🧺 Space complexity: O(k) for storing elements in the heap and additional variables.