Smallest Range Covering Elements from K Lists

HardK-way Merge · Min-Heap · Sliding Window🧩 K-Way Merge LeetCode #632 ↗Updated Oct 30, 2026

Problem

You have k lists of integers, each sorted in non-decreasing order. Find the smallest range [a, b] that contains at least one number from every list. A range is smaller if b - a is smaller, or, for equal widths, if a is smaller. Return it as [a, b].

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

Inputnums = [[1,2,3],[1,2,3],[1,2,3]]Output[1,1]

Inputnums = [[1,10],[2,11]]Output[1,2] (ties with [10,11], smaller start wins)

1 ≤ k ≤ 3500 · 1 ≤ list length ≤ 50 · -10⁵ ≤ values ≤ 10⁵

Try it yourself

Java

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Hold one pointer per list. The current picks form a valid range [min, max]; the only move that can shrink it is to advance the list holding the minimum. A min-heap finds that list in O(log k) while a running max tracks the top.

PatternK-Way Merge

Instinct Several sorted lists, rows or streams and you need the global order, the k-th smallest or a range: keep one cursor per list in a min-heap.

Memory hack Line up the heads, crown the smallest, then let its next-in-line step up.

Open the K-Way Merge guide →

Approaches

Brute ForceTry Every Value as the Left End

Time O(N²)Space O(1)

The best range starts at some list element a. For a fixed a, the tightest right end is the max over lists of each list's smallest element ≥ a (found by scanning). Skip a if some list has nothing ≥ it. N is the total number of elements.

Java

public int[] smallestRange(List<List<Integer>> nums) {
    int[] best = null;
    for (List<Integer> source : nums) {
        for (int a : source) {
            int b = a;
            boolean ok = true;
            for (List<Integer> list : nums) {
                Integer ceil = null; // smallest element >= a in this list
                for (int v : list) {
                    if (v >= a) { ceil = v; break; }
                }
                if (ceil == null) { ok = false; break; }
                b = Math.max(b, ceil);
            }
            if (ok && (best == null || b - a < best[1] - best[0]
                    || (b - a == best[1] - best[0] && a < best[0]))) {
                best = new int[]{a, b};
            }
        }
    }
    return best;
}

Direct and obviously correct, but each candidate rescans all N elements.

BetterMerge Everything, then Sliding Window

Time O(N log N)Space O(N)

Flatten all values into (value, listId) pairs and sort them. Now the task is “shortest window that contains every listId”: expand the right end, and while all k lists are covered, record the window and shrink from the left. Right ends only grow, so the first window of a given width has the smallest start.

Java

public int[] smallestRange(List<List<Integer>> nums) {
    int k = nums.size();
    List<int[]> all = new ArrayList<>(); // {value, listId}
    for (int id = 0; id < k; id++) {
        for (int v : nums.get(id)) all.add(new int[]{v, id});
    }
    all.sort((p, q) -> Integer.compare(p[0], q[0]));
    int[] count = new int[k];
    int covered = 0, left = 0;
    int[] best = {0, Integer.MAX_VALUE};
    for (int right = 0; right < all.size(); right++) {
        if (count[all.get(right)[1]]++ == 0) covered++;
        while (covered == k) {
            int lo = all.get(left)[0], hi = all.get(right)[0];
            if ((long) hi - lo < (long) best[1] - best[0]) best = new int[]{lo, hi};
            if (--count[all.get(left)[1]] == 0) covered--;
            left++;
        }
    }
    return best;
}

Turns it into a classic window problem, but the global sort ignores that lists are sorted.

OptimalK-way Merge: Min-Heap of List Heads + Running Max

Time O(N log k)Space O(k)

Start with the first element of every list in a min-heap and remember the largest of them. The heap top and the max bound a valid range. Pop the minimum, compare the range, then push the next element from the same list (updating the max). When any list runs out, no later range can cover it, so stop.

Java

public int[] smallestRange(List<List<Integer>> nums) {
    // heap entries: {value, listId, indexInList}
    PriorityQueue<int[]> heap = new PriorityQueue<>((p, q) -> Integer.compare(p[0], q[0]));
    int curMax = Integer.MIN_VALUE;
    for (int id = 0; id < nums.size(); id++) {
        int v = nums.get(id).get(0);
        heap.add(new int[]{v, id, 0});
        curMax = Math.max(curMax, v);
    }
    int[] best = {heap.peek()[0], curMax};
    while (true) {
        int[] top = heap.poll();
        // mins come out in non-decreasing order, so strict < keeps the smaller start
        if (curMax - top[0] < best[1] - best[0]) best = new int[]{top[0], curMax};
        List<Integer> list = nums.get(top[1]);
        if (top[2] + 1 == list.size()) break; // this list is exhausted
        int next = list.get(top[2] + 1);
        heap.add(new int[]{next, top[1], top[2] + 1});
        curMax = Math.max(curMax, next);
    }
    return best;
}

Each element enters the heap at most once; the heap stays at size k.

Pro tip

Why advance the minimum? Moving any other pointer can only raise the max while the min stays put, so the range can never shrink that way.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Value as the Left End	`O(N²)`	`O(1)`
Better	Merge Everything, then Sliding Window	`O(N log N)`	`O(N)`
Optimal	K-way Merge: Min-Heap of List Heads + Running Max	`O(N log k)`	`O(k)`

Common pitfalls

Advancing the list with the max instead of the min — the range only grows.
Using <= when updating: an equal-width range found later has a larger start.
Continuing after a list is exhausted — any further range would miss that list.

Interview tips

Frame it as “pick one element per list, minimise max − min”.
Justify the greedy: advancing the min is the only move that can improve the range.
Mention the sorted-merge + sliding-window version as an alternative mental model.

Pattern

K-way merge with a running max → choose one element from each sorted list to optimise a spread.

My notes saved in this browser