Solution: Smallest Range Covering Elements from K Lists

Statement

You are given $k$ sorted lists of integers, nums, where each list in nums is in non-decreasing order. Your task is to find the smallest range that contains at least one element from each of the $k$ lists.

A range $[a,b]$ is considered smaller than another range $[c,d]$ if $b−a<d−c$, or $a < c$ if $b-a==d-c$.

Constraints:

• nums.length $== k$

• $1 <= k <= 100$

• $1 \leq$ nums[i].length $\leq 50$

• $-10^3 \leq$ nums[i][j] $\leq10^3$

• nums[i] is sorted in a non-decreasing order.

Solution

The core idea of this solution is to find the smallest range that includes at least one number from each of the k sorted lists. Instead of generating all possible ranges across the lists, the solution uses a min heap (priority queue) to dynamically track the smallest and largest values across currently considered elements. This approach ensures that at every step, the solution maintains a potential valid range that includes one element from each list, continuously narrowing it down to the smallest possible.

The process begins by initializing a min heap (priority queue) and pushing the first element from each list into it. Along with each value, the index of the list it belongs to and its position within it are also stored in the heap. Additionally, a variable, maxVal, is maintained to keep track of the current maximum number among the values present in the heap. This is important because, at any point, the smallest range that covers all lists is defined by the current smallest and largest elements among the chosen set.

Once the heap is initialized, the solution enters a loop that continues as long as the heap contains one element from each list (i.e., the length of the heap equals the number of lists). In each iteration, the smallest value is popped from the heap — this represents the lower bound of the current candidate range. The result is updated accordingly if the current range (maxVal - minVal) is smaller than the previously recorded best range.

To maintain the invariant that the heap contains one element from each list, the next element from the list of the popped value is pushed into the heap. While doing so, maxVal is updated if the newly pushed element is larger than the current maximum. This ensures that the next potential range still includes one element from every list and remains as small as possible.

This process continues until it’s no longer possible to push the next element from one of the lists (i.e., the shortest list is exhausted). At that point, the smallest valid range is guaranteed to be identified and stored.

Let’s break down the key steps of the solution:

1. We initialize the following:

   1. A min heap pq to store tuples of the form.

   2. maxVal to track the maximum of the current elements from all lists.

   3. rangeStart and rangeEnd to store the current smallest range.

2. We push the first elements of each list to the heap, and maxVal is updated to the maximum of all these first elements.

3. We iterate while the heap contains one element from each list:

   1. Pop the smallest value (minVal) from the heap.

   2. If the range formed by minVal and maxVal is smaller than the previous best, update rangeStart and rangeEnd.

   3. If the next element exists in the list from which minVal was popped, push it into the heap, and update maxVal if needed.

4. We stop iterating once one of the lists runs out of elements.

5. The final smallest range covering at least one element from each list is returned as [rangeStart, rangeEnd].

Let’s look at the following illustration to get a better understanding of the solution: