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 Heaps

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

The key recognition signals are 'smallest range', 'covering elements from multiple lists', and 'sorted lists'. These indicate a heap-based approach because we need to efficiently track the minimum element among the current candidates from each list while knowing the maximum to evaluate the range. By always advancing the list that contributed the current minimum, we systematically explore all valid ranges without redundant checks.

Optimal Approach

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.

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

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

17while True:
  value, list_idx, idx = heapq.heappop(heap)
  if current_max - value < best_end - best_start:
      best_start, best_end = value, current_max
  if idx + 1 == len(nums[list_idx]):
      break
  next_value = nums[list_idx][idx + 1]
  heapq.heappush(heap, (next_value, list_idx, idx + 1))
  if next_value > current_max:
      current_max = next_value

Objective

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.

Key Insight

Extracting the minimum element from the heap identifies the lower bound of the current candidate range. Comparing the difference between the current maximum and this minimum allows the algorithm to track the smallest range found so far. Pushing the next element from the same list ensures that the heap always contains one element from each list, maintaining the validity of the range. Updating the current maximum when a larger element is pushed keeps the range evaluation accurate.

Interview Quick-Check

Core Logic

The loop continues until one list is exhausted, ensuring all valid ranges covering all lists are considered.

State & Boundaries

Breaking the loop when the next element index reaches the end of a list prevents invalid ranges missing elements from that list.

Common Pitfalls & Bugs

Failing to update current_max when pushing a larger next element leads to incorrect range calculations.

Complexity

Each heap operation is O(log k), and each element is processed once, resulting in O(n log k) time complexity.

Return the Smallest Range Found

32	`return [best_start, best_end]`

Objective

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

Key Insight

After the loop terminates due to exhaustion of one list, the recorded best_start and best_end represent the smallest range that includes at least one element from each list. Returning this range completes the solution.

Interview Quick-Check

Core Logic

Returning the best range found ensures the output satisfies the problem's requirement of covering all lists.

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.

Line 20 Critical

if current_max - value < best_end - best_start:

Check if the current range is smaller than the best recorded range.

Comparing the current range to the best ensures the algorithm tracks the smallest valid range found so far.

Line 23 Critical

if idx + 1 == len(nums[list_idx]):

Check if the next element index exceeds the length of the current list.

Detecting exhaustion of a list signals that no further valid ranges including all lists can be found, so the loop must terminate.

Line 24 Critical

break

Break the loop if any list is exhausted.

Terminating the loop prevents invalid ranges that exclude elements from the exhausted list, maintaining correctness.

Line 27 Critical

heapq.heappush(heap, (next_value, list_idx, idx + 1))

Push the next element from the same list into the heap.

Adding the next element ensures the heap remains representative of the current candidates from all lists, allowing the algorithm to explore new ranges.

Line 29 Critical

if next_value > current_max:

Update current_max if the next element is greater.

Maintaining an accurate current_max is essential for correct range calculations as the heap elements change.

Line 30 Critical

current_max = next_value

Set current_max to the maximum of itself and the next element.

This update ensures the upper bound of the candidate range reflects the largest element currently in the heap.

Line 10 Core

heap.append((value, list_idx, 0))

Append a tuple of (value, list index, element index) to the heap list.

Storing the element along with its list and position indices enables tracking and advancing through each list during heap operations.

Line 14 Core

heapq.heapify(heap)

Transform the list into a heap in-place.

Heapifying the list organizes it into a min-heap structure, enabling efficient extraction of the smallest element in O(log k) time.

Line 15 Core

best_start, best_end = heap[0][0], current_max

Initialize the best range start and end using the smallest heap element and current_max.

Setting the initial best range to the current minimum and maximum establishes a baseline for comparison as the algorithm progresses.

Line 21 Core

best_start, best_end = value, current_max

Update the best range start and end to the current range.

Recording the improved range preserves the optimal solution discovered during iteration.

Line 26 Core

next_value = nums[list_idx][idx + 1]

Retrieve the next element from the same list.

Advancing to the next element in the list maintains the invariant that the heap contains one element from each list, enabling continuous range evaluation.

Line 32 Core

return [best_start, best_end]

Return the smallest range found as a list [best_start, best_end].

Returning the recorded best range completes the algorithm, providing the required output that covers all lists with the smallest possible range.

Line 5 Core

heap = []

Initialize an empty list to serve as the min-heap.

The heap will store the current candidate elements from each list, enabling efficient extraction of the minimum element at each step.

Line 6 Core

current_max = float("-inf")

Initialize current_max to negative infinity to track the maximum value among heap elements.

Setting current_max to negative infinity ensures that any first element encountered will update it correctly, establishing a valid initial maximum for range calculations.

Line 9 Standard

value = row[0]

Extract the first element from the current list.

The first element serves as the initial candidate from this list to be included in the heap and range evaluation.

Line 17 Standard

while True:

Start an infinite loop to process heap elements.

The loop continues extracting and updating ranges until one list is exhausted, ensuring all valid ranges are considered.

Line 8 Standard

for list_idx, row in enumerate(nums):

Iterate over each list with its index.

Enumerating the lists allows tracking the origin of each element pushed into the heap, which is essential for pushing subsequent elements from the same list.

Test Your Understanding

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

Because the range must include at least one element from each list, once a list is exhausted, no further ranges can include elements from that list, so continuing would violate the problem's requirement.

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]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Min-Heap and Track Initial Maximum

Iteratively Extract Minimum and Update Smallest Range

Return the Smallest Range Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.