HardArrayHash TableGreedySliding WindowSortingHeap (Priority Queue)

Smallest Range Covering Elements from K Lists

1 approach, code in every language

You are given k lists of integers, each sorted in non-decreasing order. Find the smallest range [a, b] that includes at least one number from each of the k lists.

A range [a, b] is smaller than another range [c, d] if b - a is smaller than d - c, or if the widths are equal and a is smaller than c.

Return the smallest such range as a two-element list.

Example 1

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

Output: [20,24]

24 comes from the first list, 20 from the second, and 22 from the third. The range [20,24] has width 4 and no narrower range covers all three lists.

Example 2

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

Output: [1,1]

The value 1 exists in every list, so the range [1,1] of width 0 already covers all lists.

Constraints

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

Min-Heap with Running Maximum

Hold one pointer per list in a min-heap and track the current maximum to size the range.

Loading animation…

Intuition

We need a window [a, b] that touches every list at least once, and among all such windows we want the narrowest. If we hold exactly one candidate element from each list, the window covering them is [min, max] of the held elements. The lower bound is the smallest held element, so to possibly shrink the window we must advance the list that owns that minimum to its next larger value. A min-heap gives us the current minimum in O(log k), and we track the running maximum separately so the current range is always [heap-min, currentMax]. We record the best range each step and stop as soon as any list runs out, because that list can no longer be covered.

Algorithm walkthrough

1Push the first element of each list into a min-heap as (value, listIndex, elementIndex), and track the maximum of these first elements as currentMax.
2The current covering range is [heap minimum, currentMax]; if it is narrower than the best seen, record it.
3Pop the minimum element from the heap.
4If its list has a next element, push that element and update currentMax; otherwise stop, since this list can no longer be represented.
5Repeat, always keeping exactly one element per list in the heap until one list is exhausted.
6Return the best range found.

Implementation

import heapq

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        heap = []
        current_max = float('-inf')
        for i, arr in enumerate(nums):
            heap.append((arr[0], i, 0))
            current_max = max(current_max, arr[0])
        heapq.heapify(heap)

        best = [float('-inf'), float('inf')]
        while heap:
            val, i, j = heapq.heappop(heap)
            if current_max - val < best[1] - best[0]:
                best = [val, current_max]
            if j + 1 == len(nums[i]):
                break
            next_val = nums[i][j + 1]
            current_max = max(current_max, next_val)
            heapq.heappush(heap, (next_val, i, j + 1))
        return best

Time

O(N log k)

Space

O(k)

N is the total number of elements across all lists and k is the number of lists. Every element is pushed and popped at most once at O(log k) each, and the heap holds exactly one element per list.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Tightest Gauge Band is our own problem on the technique behind Smallest Range Covering Elements from K Lists: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free