Module 3 · Merge Pattern

Smallest Range Covering Elements from K Lists

HardProblem 6 of 14 11 min read ~35 min to solve LeetCode

HeapPriority QueueK-Way MergeGreedySliding Window

Asked atGoogleAmazonMicrosoftMetaBloomberg

Problem Statement

You are given k sorted integer lists. Return the smallest inclusive range [left, right] such that at least one number from each list lies inside the range. A range is smaller if it has a shorter length, or if tied, a smaller left endpoint.

Input

A list of k sorted integer lists, where every inner list has at least one value.

Output

An integer array [left, right] representing the smallest inclusive range that contains at least one value from every list.

Constraints

•nums.length == k
•1 <= k <= 3500
•1 <= nums[i].length <= 50
•-10^5 <= nums[i][j] <= 10^5
•nums[i] is sorted in non-decreasing order

Examples

Example 1

Input:

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

Output: [20,24]

Explanation: The range includes **24** from the first list, **20** from the second list, and **22** from the third list. No shorter valid range covers all three lists.

Example 2

Input:

nums = [[1,2,3],[1,2,3],[1,2,3]]

Output: [1,1]

Explanation: The value **1** appears in every list, so the zero-width range **[1,1]** already covers all lists.

Learning Objectives

Recognise the range version of k-way merge: keep one active element from each sorted list.
Track a running maximum while the min-heap provides the current minimum.
Explain why advancing the current minimum is the only move that can shrink the active range.
Stop correctly when any list is exhausted because coverage of all lists is no longer possible.

Intuition

Pattern Recognition

The signal is k sorted lists plus a range that must include one element from every list. If you choose one active value from each list, those k values define a valid range from their minimum to their maximum. A min-heap can reveal the current minimum, while a running curMax remembers the current maximum.

The key greedy insight is that the only useful move is advancing the list that owns the minimum. The current range is [min, curMax]. Advancing any non-minimum element cannot increase the left boundary, so it cannot shrink the range from the left; it can only keep or raise the maximum. To get a tighter range, the minimum must move right, so we poll the minimum and replace it with the next element from that same list.

Common mistakes

×Advancing the list with the current maximum, which usually makes the right boundary stay high or move higher without improving the left boundary.
×Forgetting to update **curMax** when the pushed next value is larger than every active value seen so far.
×Continuing after one list is exhausted, even though the active set no longer covers every list.
×Tracking only heap values and not the list index and element index needed to advance the correct list.

Algorithm Explanation

Key idea

Maintain exactly one active element from each list. The min-heap is ordered by active value, so its root is the current left boundary. A separate curMax is the current right boundary. The active window covers all lists, so it is always a candidate range. After recording it, advance the list that contributed the minimum because that is the only move that can raise the left boundary and possibly shrink the range.

Heap walkthrough

For nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], initialise with 4 from list 0, 0 from list 1, and 5 from list 2. The heap is [0 from list 1, 4 from list 0, 5 from list 2] and curMax = 5, so the first candidate is [0,5]. Poll the minimum 0 and push 9 from that same list. Now the heap is [4 from list 0, 5 from list 2, 9 from list 1] and curMax = 9, giving candidate [4,9].

Poll 4 and push 10, moving curMax to 10. The heap becomes [5 from list 2, 9 from list 1, 10 from list 0] and the range is [5,10]. Poll 5 and push 18, so curMax = 18 and the range widens to [9,18]. The process keeps raising the minimum. Eventually the active values become 20 from list 1, 22 from list 2, and 24 from list 0, with curMax = 24. The range [20,24] is shorter than all previous candidates, so it becomes the answer. Polling 20 would exhaust list 1, so the search stops.

Algorithm

Create a min-heap of entries containing value, list index, and element index.
Push the first element from every list and set curMax to the largest of those first elements.
Initialise the best range from the heap minimum to curMax.
While the heap still contains one entry from every list, compare the current range [heap minimum, curMax] with the best range.
Poll the heap minimum. If that element has no successor in its list, stop.
Push the successor from the same list and update curMax if the successor is larger.
Return the best range recorded.

Solutions

Solution: Min-heap with running maximum

When to prefer this:

Use this when every list is sorted and the range must cover all lists simultaneously. It is the standard interview solution because it keeps exactly one active candidate per list.

Store one entry from each list in a min-heap and track the maximum active value separately. The heap root and curMax define the current covering range. After evaluating it, advance the list that owns the minimum and stop as soon as that list has no next value.

Step-by-step

Offer the first value from each list into the min-heap, storing its list and element positions.
Track currentMax as the largest offered value.
While the heap covers all lists, peek or poll the smallest active value and compare [smallest, currentMax] with the best answer.
Advance only the list that supplied the smallest value.
If that list is exhausted, break because a valid range can no longer include every list.
Otherwise offer the next value from that list and update currentMax.
Return the best recorded range.

Time

O(N log k)

Space

O(k)

N total values may each be pushed and polled once, while the heap stores one active value per list.

Java implementation

Loading…

Dry Run

Sample input

nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]. Track one active value from each list, the heap minimum, and curMax.

step	polled minimum	heap values after push	curMax	best range
start	none	[0 from L1, 4 from L0, 5 from L2]	5	[0,5]
1	0 from L1	[4 from L0, 5 from L2, 9 from L1]	9	[0,5]
2	4 from L0	[5 from L2, 9 from L1, 10 from L0]	10	[0,5]
3	5 from L2	[9 from L1, 10 from L0, 18 from L2]	18	[0,5]
4	9 from L1	[10 from L0, 12 from L1, 18 from L2]	18	[0,5]
5	10 from L0	[12 from L1, 15 from L0, 18 from L2]	18	[0,5]
6	12 from L1	[15 from L0, 18 from L2, 20 from L1]	20	[0,5]
7	15 from L0	[18 from L2, 20 from L1, 24 from L0]	24	[0,5]
8	18 from L2	[20 from L1, 22 from L2, 24 from L0]	24	[20,24]
9	20 from L1	list L1 exhausted, stop	24	[20,24]

The best range only improves when the left boundary has advanced far enough. Once list L1 is exhausted, no future active set can contain one value from every list, so [20,24] is final.

Interview Tips

Do not present this as a generic sliding window over a flattened array unless you also explain why sorted order by source list matters. The concise proof is the minimum-advance argument: with active values covering every list, moving anything except the minimum cannot improve the left boundary, so the only candidate-changing move that may shrink the range is to advance the list that owns the minimum.

Likely follow-ups

How would you solve this by flattening all values with their list ids and using a sliding window over the sorted flattened list?
How should ties be handled when two ranges have the same length?
What changes if each list is a lazy stream rather than an in-memory array?
How would you return all minimum-length ranges instead of just one?

Key Takeaways

One active value from every list defines a valid covering range.
The min-heap gives the left boundary while **curMax** stores the right boundary.
Advancing the current minimum is the only move that can raise the left boundary and possibly shrink the range.
The search stops when any list is exhausted because coverage of all lists becomes impossible.

Reusable template: Range over k sorted lists: maintain one active element per list, evaluate [heap minimum, current maximum], then advance only the list that owns the minimum.