MANG Problem #30: Smallest Range Covering Elements from K Lists (Hard)

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

A range [a, b] is smaller than [c, d] if b - a < d - c or if b - a == d - c and a < c.

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

2. Approach: Min-Heap + Max Tracking

Since we need one number from every list, we can start with the heads of all $K$ lists. This forms our first valid range: [min(heads), max(heads)].

Initialize: Push the first element of each list into a Min-Heap. Track the maximum value currently in the heap (maxVal).
Iterate:
- The range is [heap.peek().val, maxVal]. Update our globalSmallestRange if this is smaller.
- Pop the smallest element from the heap.
- Push the next element from the same list into the heap.
- Update maxVal with this new element.
Termination: If any list is exhausted, we can no longer form a range containing elements from all $K$ lists.

3. Java Implementation

public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    int max = Integer.MIN_VALUE;
    
    // 1. Initialize heap with first elements
    for (int i = 0; i < nums.size(); i++) {
        int val = nums.get(i).get(0);
        pq.offer(new int[]{val, i, 0}); // {value, listIndex, elementIndex}
        max = Math.max(max, val);
    }
    
    int start = 0, end = Integer.MAX_VALUE;
    
    while (pq.size() == nums.size()) {
        int[] curr = pq.poll();
        int min = curr[0];
        
        // 2. Update smallest range
        if (max - min < end - start) {
            start = min;
            end = max;
        }
        
        // 3. Move forward in the list that provided the min value
        if (curr[2] + 1 < nums.get(curr[1]).size()) {
            int nextVal = nums.get(curr[1]).get(curr[2] + 1);
            pq.offer(new int[]{nextVal, curr[1], curr[2] + 1});
            max = Math.max(max, nextVal);
        } else {
            break; // One list is exhausted
        }
    }
    return new int[]{start, end};
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: At any point, the heap contains one candidate from every list. The range defined by the min (heap top) and the max we've tracked is a valid candidate.
The Squeeze: To make the range smaller, our only option is to increase the min. We do this by popping the smallest value and replacing it with the next value from that same list.
Why we stop: Once any list is empty, we can't "replace" the minimum anymore. Any further range would be missing an element from that exhausted list.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(N log K) where N is the total number of elements and K is the number of lists. Every element is pushed/popped once."
Interviewer: "How is this related to Sliding Window?"
You: "We are essentially sliding a window across the $K$ sorted streams. The heap allows us to find the window's left boundary efficiently while we track the right boundary with maxVal."