How do you solve Smallest Range Covering Elements from K Lists?

Initialize a min-heap with the first element from each list and track the current maximum value among these elements. Repeatedly pop the smallest element from the heap and update the best range if the current range (current_max - min_element) is smaller. Then, push the next element from the same list into the heap and update the current maximum if needed. Stop when any list is exhausted. This approach guarantees the smallest range covering all lists in O(n log k) time, where n is the total number of elements and k is the number of lists.

Smallest Range Covering Elements from K Lists

Q: What is the time complexity of Smallest Range Covering Elements from K Lists?

O(n log k). Each of the n elements across all lists is pushed and popped from the heap at most once. The heap size is at most k, so each push/pop operation costs O(log k), resulting in O(n log k) total time.

Q: What pattern does Smallest Range Covering Elements from K Lists use?

The Pattern: Heap / Priority Queue (K-Way Merge with Range Tracking) The Heuristic: When merging multiple sorted lists to find a global property involving minimum and maximum elements, use a min-heap to track the smallest current element and maintain a running maximum to evaluate candidate ranges efficiently.

Hard Heap / Priority Queue

Problem

Given a list of k sorted integer lists, return the smallest range [start, end] such that at least one number from each list falls within this range.

nums.length == k
1 ≤ k ≤ 3500
1 ≤ nums[i].length ≤ 50
−10⁵ ≤ nums[i][j] ≤ 10⁵
nums[i] is sorted in ascending order

Example

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

Output: [20,24]

The brute-force approach would consider all possible ranges formed by picking one element from each list, which is computationally infeasible due to combinatorial explosion. The optimal strategy uses a min-heap to track the current smallest elements from each list and a variable to track the current maximum among these elements. Initially, the heap contains the first element of each list. The algorithm repeatedly extracts the minimum element from the heap and attempts to improve the range by pushing the next element from the same list into the heap, updating the current maximum if necessary. The critical moment occurs when one list is exhausted, signaling that no smaller range covering all lists can be found. The smallest range recorded during this process is returned.

Approach

Straightforward Solution

A brute-force approach would generate all combinations of elements from each list and compute their ranges, resulting in exponential time complexity and infeasible performance.

Core Observation

The smallest range covering at least one element from each list must include at least one element from each list simultaneously. Tracking the minimum and maximum elements among the current candidates from each list allows us to evaluate candidate ranges efficiently.

Path to Optimal

Preview

The key recognition signals are 'smallest range', 'covering elements from multiple lists', and 'sorted lists'…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a min-heap with the first element from each list and track the current maximum value among these elements. Repeatedly pop the smallest element from the heap and update the best range if the current range (current_max - min_element) is smaller…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log k)

Each of the n elements across all lists is pushed and popped from the heap at most once. The heap size is at most k, so each push/pop operation costs O(log k), resulting in O(n log k) total time.

Space

O(k)

The heap stores at most one element from each of the k lists at any time, resulting in O(k) auxiliary space. This space is necessary to track the current candidates from each list.

Pattern Spotlight

Heap / Priority Queue (K-Way Merge with Range Tracking)

When merging multiple sorted lists to find a global property involving minimum and maximum elements, use a min-heap to track the smallest current element and maintain a running maximum to evaluate candidate ranges efficiently.

Solution

Python

1import heapq
2
3class Solution:
4    def smallestRange(self, nums: List[List[int]]) -> List[int]:
5        heap = []
6        current_max = float("-inf")
7
8        for list_idx, row in enumerate(nums):
9            value = row[0]
10            heap.append((value, list_idx, 0))
11            if value > current_max:
12                current_max = value
13
14        heapq.heapify(heap)
15        best_start, best_end = heap[0][0], current_max
16
17        while True:
18            value, list_idx, idx = heapq.heappop(heap)
19
20            if current_max - value < best_end - best_start:
21                best_start, best_end = value, current_max
22
23            if idx + 1 == len(nums[list_idx]):
24                break
25
26            next_value = nums[list_idx][idx + 1]
27            heapq.heappush(heap, (next_value, list_idx, idx + 1))
28
29            if next_value > current_max:
30                current_max = next_value
31
32        return [best_start, best_end]

Step-by-Step Solution

Initialize Min-Heap and Track Initial Maximum

5heap = []
6current_max = float("-inf")
8for list_idx, row in enumerate(nums):
9    value = row[0]
10    heap.append((value, list_idx, 0))
11    if value > current_max:
12        current_max = value
14heapq.heapify(heap)
15best_start, best_end = heap[0][0], current_max

Objective

To prepare the min-heap with the first element from each list and determine the initial maximum value among these elements.

Key Insight

By pushing the first element of each list into the heap, the algorithm sets up a window containing one candidate from each list. Tracking the maximum among these initial elements is crucial because the range is defined by the minimum (top of the heap) and this maximum. This setup enables efficient range evaluation and incremental updates as the algorithm progresses.

Interview Quick-Check

Core Logic

The heap stores tuples of (value, list index, element index) to track the origin of each element, enabling pushing the next element from the same list.

State & Boundaries

The initial current_max is set to negative infinity and updated to the maximum of the first elements to correctly represent the initial range.

Common Pitfalls & Bugs

Forgetting to update current_max when adding initial elements leads to incorrect range calculations.

Iteratively Extract Minimum and Update Smallest Range

To repeatedly extract the smallest element from the heap, update the best range if improved, and push the next element from the same list while maintaining the current maximum.

Return the Smallest Range Found

To output the smallest range [best_start, best_end] after processing all valid candidate ranges.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 9 Critical lines interviewers watch for.

Line 18 Critical

value, list_idx, idx = heapq.heappop(heap)

Pop the smallest element from the heap.

Extracting the minimum element identifies the current lower bound of the candidate range, enabling range evaluation and advancement of the corresponding list.

Line 11 Critical

if value > current_max:

Update current_max if the current value is greater.

Maintaining the maximum value among the current heap elements is critical for correctly evaluating the range between the minimum and maximum elements.

Line 12 Critical

current_max = value

Update current_max to the maximum of itself and the current value.

This ensures current_max always reflects the largest element currently in the heap, which defines the upper bound of the candidate range.

Full line-by-line criticality + rationale for all 20 lines available on Pro.

Test Your Understanding

Why does the algorithm stop when any one list is exhausted during the heap processing?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Smallest Range Covering Elements from K Lists from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Smallest Range Covering Elements from K Lists drill

or drill a free problem

5	`heap = []`
6	`current_max = float("-inf")`
8	`for list_idx, row in enumerate(nums):`
9	`value = row[0]`
10	`heap.append((value, list_idx, 0))`
11	`if value > current_max:`
12	`current_max = value`
14	`heapq.heapify(heap)`
15	`best_start, best_end = heap[0][0], current_max`

1	`import heapq`
2
3	`class Solution:`
4	`def smallestRange(self, nums: List[List[int]]) -> List[int]:`
5	`heap = []`
6	`current_max = float("-inf")`
7
8	`for list_idx, row in enumerate(nums):`
9	`value = row[0]`
10	`heap.append((value, list_idx, 0))`
11	`if value > current_max:`
12	`current_max = value`
13
14	`heapq.heapify(heap)`
15	`best_start, best_end = heap[0][0], current_max`
16
17	`while True:`
18	`value, list_idx, idx = heapq.heappop(heap)`
19
20	`if current_max - value < best_end - best_start:`
21	`best_start, best_end = value, current_max`
22
23	`if idx + 1 == len(nums[list_idx]):`
24	`break`
25
26	`next_value = nums[list_idx][idx + 1]`
27	`heapq.heappush(heap, (next_value, list_idx, idx + 1))`
28
29	`if next_value > current_max:`
30	`current_max = next_value`
31
32	`return [best_start, best_end]`