Smallest Range Covering K Lists

HardK-Way MergeSeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given k lists of integers, each sorted in non-decreasing order. Find the smallest range [a, b] that includes at least one number from every list. Range [a, b] is smaller than [c, d] if b - a < d - c, or if the widths are equal and a < c. Both ends are inclusive, so [a, a] is a valid range of width 0. Return the range as [a, b].

Examples

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

[20,24] includes 24 from the first list, 20 from the second and 22 from the third, for a width of 4. No other range of width 4 or less covers all three lists.

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

Every list contains 1, so [1,1] covers all three with width 0. [2,2] and [3,3] also have width 0, but 1 is the smaller start.

Constraints

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50

Hints

Hint 1

The range must touch every list, so it's pinned by the smallest current value across all lists and the largest one, how can you keep both?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Keep one position in each list, a min-heap of the values at those positions, and the largest of them. The heap's minimum and that maximum always form a range touching every list. Pop the minimum, record the range if it's strictly narrower than the best so far, then advance that list and push its next value, updating the maximum. Moving the minimum is the only move that can shrink the range. Stop once any list runs out. O(N log k) time, O(k) space, N = total count of numbers.

Time

O(N log k)

Space

O(k)

Pitfall

Continuing after a list runs out: once the popped minimum has no next value, no later range can include that list, so the loop must end. Compare widths with a strict <, so a later range of equal width can't replace one with a smaller start.

Solutions

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            heap.offer(new int[]{ v, i, 0 });
            curMax = Math.max(curMax, v);
        }
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;
        while (heap.size() == nums.size()) {
            int[] top = heap.poll();
            int v = top[0], li = top[1], ei = top[2];
            if (curMax - v < rangeEnd - rangeStart) {
                rangeStart = v;
                rangeEnd = curMax;
            }
            if (ei + 1 < nums.get(li).size()) {
                int nextV = nums.get(li).get(ei + 1);
                heap.offer(new int[]{ nextV, li, ei + 1 });
                curMax = Math.max(curMax, nextV);
            }
        }
        return new int[]{ rangeStart, rangeEnd };
    }
}

import heapq

class Solution:
    def smallestRange(self, nums):
        heap = []
        cur_max = float("-inf")
        for i, lst in enumerate(nums):
            heapq.heappush(heap, (lst[0], i, 0))
            cur_max = max(cur_max, lst[0])
        range_start, range_end = 0, float("inf")
        while len(heap) == len(nums):
            v, li, ei = heapq.heappop(heap)
            if cur_max - v < range_end - range_start:
                range_start, range_end = v, cur_max
            if ei + 1 < len(nums[li]):
                nxt = nums[li][ei + 1]
                heapq.heappush(heap, (nxt, li, ei + 1))
                cur_max = max(cur_max, nxt)
        return [range_start, range_end]