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

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #30: Smallest Range Covering Elements from K Lists (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

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.