Smallest Range Covering Elements from K Lists - Video Solutions

Problem Overview: You are given k sorted lists of integers. The goal is to find the smallest numerical range [a, b] such that each list contributes at least one element inside that range. If multiple ranges have the same width, the one with the smaller start value is preferred.

Approach 1: Flatten + Sliding Window (Sorting) (Time: O(N log N), Space: O(N))

Combine all elements from the k lists into a single array of pairs (value, listIndex). Sort this array by value using sorting. Now apply a sliding window across the sorted array while tracking how many unique lists are covered inside the window. Expand the right pointer to include elements and shrink the left pointer once all k lists are represented. Each valid window forms a candidate range. Update the best range whenever the window length becomes smaller.

Approach 2: Min-Heap with K Pointers (Greedy) (Time: O(N log K), Space: O(K))

This is the optimal solution and uses a min-heap (priority queue). Insert the first element from each list into the heap along with its list index and element index. Track the current maximum value among these elements. The heap always exposes the smallest value across the lists. That smallest value forms the left boundary of the candidate range while the tracked maximum forms the right boundary. Pop the smallest element, push the next element from the same list, and update the maximum if needed. The moment one list runs out of elements, you stop because every valid range must include one element from each list.

Approach 3: Tracking Indices of Current Elements (Multi-Pointer) (Time: O(N log K), Space: O(K))

Maintain an index pointer for each list. At every step, compute the minimum and maximum values among the current pointers. That pair forms the current candidate range. Move the pointer belonging to the minimum value because expanding the smaller boundary is the only way to possibly reduce the range width. Efficient implementations use a heap to quickly identify the smallest pointer value while maintaining the current maximum. The process continues until any pointer reaches the end of its list.

Recommended for interviews: The min-heap greedy solution is what interviewers typically expect. It demonstrates strong understanding of heaps, multi-list merging patterns, and greedy range updates. The flatten + sliding window technique is easier to reason about and proves correctness, but the heap approach improves the time complexity from O(N log N) to O(N log K), which matters when many lists are involved.