LeetCode 632: Smallest Range Covering Elements from K Lists

Problem Restatement

We are given k sorted lists of integers.

We need to find the smallest range [a, b] such that the range contains at least one number from every list.

A number x is inside the range [a, b] if:

a <= x <= b

A range [a, b] is smaller than another range [c, d] if:

b - a < d - c

If both ranges have the same length, choose the one with the smaller start value a.

Input and Output

Constraints:

Examples

Example 1:

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

The answer is:

[20, 24]

Why?

So [20, 24] covers all three lists.

Example 2:

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

The answer is:

[1, 1]

The range [1, 1] contains 1 from every list.

First Thought: Check All Ranges

A direct idea is to consider every possible pair [a, b] from all numbers in all lists.

For each range, check whether it contains at least one value from each list.

This works, but it is too slow.

Let N be the total number of values across all lists. There can be many candidate ranges, and checking each range against all lists is expensive.

We need to exploit the fact that each list is already sorted.

Key Insight

At any moment, suppose we choose one current number from each list.

Then those k numbers define a valid range:

minimum chosen value to maximum chosen value

For example, if the current chosen values are:

4, 0, 5

then the current range is:

[0, 5]

This range covers all lists because it was built from one number from each list.

To improve the range, we should move the list that currently has the minimum value.

Why?

The current maximum value already fixes the right side of the range. If we move any list other than the minimum one, the minimum stays the same, so the range cannot get smaller. The only way to possibly increase the left boundary and shrink the range is to advance the list that owns the current minimum.

This is a k-way merge idea.

We use a min-heap to find the current minimum efficiently, and we keep a variable current_max for the current maximum.

Algorithm

1. Put the first element of every list into a min-heap.
2. Track the maximum value among these first elements.
3. The heap minimum and current_max form a valid range.
4. Pop the minimum value from the heap.
5. Advance in the same list from which that minimum came.
6. Push the next value from that list into the heap.
7. Update current_max.
8. Repeat until one list has no next value.

When one list is exhausted, we stop. After that point, we can no longer form a range that includes every list.

Implementation

import heapq

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        heap = []
        current_max = float("-inf")

        for list_index, arr in enumerate(nums):
            value = arr[0]
            heapq.heappush(heap, (value, list_index, 0))
            current_max = max(current_max, value)

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

        while True:
            current_min, list_index, element_index = heapq.heappop(heap)

            if current_max - current_min < best_end - best_start:
                best_start = current_min
                best_end = current_max

            next_index = element_index + 1

            if next_index == len(nums[list_index]):
                break

            next_value = nums[list_index][next_index]
            heapq.heappush(heap, (next_value, list_index, next_index))
            current_max = max(current_max, next_value)

        return [best_start, best_end]

Code Explanation

The heap stores triples:

(value, list_index, element_index)

This tells us:

We initialize the heap with the first value from each list:

for list_index, arr in enumerate(nums):
    value = arr[0]
    heapq.heappush(heap, (value, list_index, 0))
    current_max = max(current_max, value)

At this point, the heap has one value from every list, so it defines a valid range.

The smallest current value is at the top of the heap:

current_min, list_index, element_index = heapq.heappop(heap)

The current range is:

[current_min, current_max]

If this range is smaller than the best known range, we update the answer:

if current_max - current_min < best_end - best_start:
    best_start = current_min
    best_end = current_max

When lengths are equal, we do not update. Since the process sees ranges in increasing left-bound order, keeping the earlier range preserves the smaller start tie-break.

Then we advance in the same list:

next_index = element_index + 1

If that list is exhausted, we stop:

if next_index == len(nums[list_index]):
    break

Otherwise, we push the next value and update current_max:

next_value = nums[list_index][next_index]
heapq.heappush(heap, (next_value, list_index, next_index))
current_max = max(current_max, next_value)

Correctness

At every iteration, the heap contains exactly one chosen element from each list. Therefore, the interval from the heap minimum to current_max contains at least one element from every list, so it is a valid range.

Consider the current range [current_min, current_max]. The left endpoint comes from the list at the top of the heap. If we do not advance this list, then the minimum chosen value remains current_min. Advancing any other list cannot increase the left endpoint, so it cannot produce a smaller range with the current choices.

Therefore, the only useful next move is to advance the list that owns the current minimum.

The algorithm repeatedly performs exactly this move. Since each list is sorted, advancing a list moves its chosen value forward in non-decreasing order. This enumerates all candidate ranges that can be optimal under the k-way merge process.

Whenever a valid range is seen, the algorithm compares it with the best known range and keeps the smaller one. If the length is equal, it keeps the earlier start value.

When some list is exhausted, no future range can include an element from every list, because that list has no remaining candidate to choose. So stopping is correct.

Thus the returned range is the smallest valid range.

Complexity

Let N be the total number of elements across all lists, and let k be the number of lists.

Alternative Solution: Merge Then Sliding Window

Another way is to flatten all numbers into one array while remembering which list each number came from.

Then sort that array and use a sliding window to find the smallest window that contains all k list IDs.

from collections import defaultdict

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        merged = []

        for list_index, arr in enumerate(nums):
            for value in arr:
                merged.append((value, list_index))

        merged.sort()

        count = defaultdict(int)
        covered = 0
        left = 0

        best_start = -10**9
        best_end = 10**9

        for right, (right_value, right_list) in enumerate(merged):
            if count[right_list] == 0:
                covered += 1
            count[right_list] += 1

            while covered == len(nums):
                left_value, left_list = merged[left]

                if right_value - left_value < best_end - best_start:
                    best_start = left_value
                    best_end = right_value

                count[left_list] -= 1
                if count[left_list] == 0:
                    covered -= 1

                left += 1

        return [best_start, best_end]

This solution is also correct, but it uses more memory because it stores all values.

Testing

def run_tests():
    s = Solution()

    assert s.smallestRange([
        [4, 10, 15, 24, 26],
        [0, 9, 12, 20],
        [5, 18, 22, 30],
    ]) == [20, 24]

    assert s.smallestRange([
        [1, 2, 3],
        [1, 2, 3],
        [1, 2, 3],
    ]) == [1, 1]

    assert s.smallestRange([
        [1],
        [2],
        [3],
    ]) == [1, 3]

    assert s.smallestRange([
        [-5, -4],
        [-3, -2],
        [-1],
    ]) == [-5, -1]

    assert s.smallestRange([
        [1, 5, 8],
        [4, 12],
        [7, 8, 10],
    ]) == [4, 7]

    print("all tests passed")

run_tests()

Test meaning: