What is the brute force approach and complexity for Smallest Range Covering Elements from K Lists?

For each value lo, binary search every list for its first value ≥ lo; keep the narrowest range with time complexity O(N · k log n) and space complexity O(1).

What is the optimal approach and complexity for Smallest Range Covering Elements from K Lists?

Keep one value per list in a min-heap and track the largest; the range is [heap top, largest] with optimal time complexity O(N log k) and space complexity O(k).

How do you identify the pattern for Smallest Range Covering Elements from K Lists?

Look for key signals in the prompt: "smallest range" indicates A start and an end judged by width: the minimum-width window that touches many lists.; "at least one number from every list" indicates Every list must be represented, so keep one candidate per list at a time.; "sorted lists" indicates Each list's next value is its next bigger one, so each candidate can move forward on its own..

Smallest Range Covering Elements from K Lists

Hard·LeetCode #632Interview-Level

LeetCode

Jump:

30-Second Mental ModelK-way Merge — Smallest range (min-heap with one value per list, plus curMax)

Complexity:O(N · k log n)→O(N log k)

Key Insight

Keep exactly one value from each list in a min-heap, and track curMax, the largest value in the heap. The heap top is the smallest, so the range is [heap top, curMax]. Only the smallest value can start a better range, so remove it and bring in the next value from the same list, updating curMax. Stop when a list runs out.

Core Validity Invariant

The range [heap top, curMax] is valid because the heap holds exactly one value from every list, so every list has a value between the smallest and the largest.

Problem

You get k lists of integers. Every list is sorted from smallest to largest.

Find the smallest range [a, b] such that every list has at least one number between a and b, with both ends included.

A range is smaller when its width b − a is smaller. If two ranges have the same width, the one with the smaller start a wins.

Input

nums: a list of k sorted lists of integers.

Output

The smallest range, as two numbers [a, b].

Example 1

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

Output: [20, 24]

The range holds 24 from list 0, 20 from list 1 and 22 from list 2. Its width is 4, and no other range that covers all three lists is narrower.

Example 2

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

Output: [1, 1]

The value 1 is in every list, so the range [1, 1] has width 0.

Example 3

Input: nums = [[1, 5], [2, 6]]

Output: [1, 2]

[1, 2] and [5, 6] both have width 1. They tie, so the one with the smaller start, [1, 2], is the answer.

Constraints

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

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The range must contain a number from every list. If I fix the start of the range, what is the least the range has to reach in each list?
2.
Does the start of the answer have to be one of the numbers in the lists?
3.
If I put all the numbers on one sorted line, which parts of that line can count as a range that touches every list?
4.
If I keep only one number from each list at a time, how do I find the smallest of them fast? What happens to the others?
5.
Suppose the range starts at the smallest number I currently hold. If I move a different list forward, can the range get narrower?
6.
When one list runs out of numbers, can any range I have not checked yet still cover that list?

Brute force approach

Idea

Try every value in the lists as the start lo. For that start, each list offers its smallest value that is ≥ lo, found by binary search. The range must reach the largest of those values, so hi is that maximum. Keep the narrowest [lo, hi] seen, and on a tie keep the smaller lo.

Thinking process

1
Any range starts at some value that is in the lists. So I can try each one as the start.
2
Fix the start at lo. To cover a list, I need a value in it that is ≥ lo. The smallest such value is the cheapest choice, so the range has to reach at least that far.
3
Check with real numbers: lo = 4, the first value of list 0. The first values ≥ 4 in the three lists are 4, 9 and 5. The largest is 9, so [4, 9] covers every list with width 5.
4
Each list is sorted, so 'the first value ≥ lo' is a binary search (lower_bound). If some list has no value ≥ lo, this start fails and I skip it.
5
Keep the narrowest range. If two ranges have the same width, keep the one with the smaller start.

Visual

Each value is tried as the range start lo. In every list, a binary search finds the smallest value ≥ lo (blue cell, pointer lb). Blue shading = the range [lo, hi]. The searches are redone from scratch for every start.

Brute force: search every list for every startnums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]step 1/15

Work

starts to try: 13
binary searches: 0

Try every value as the range start lo

There are 13 values, so there are 13 possible starts. For each start, every list gets its own search.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> best;
        long long bestWidth = LLONG_MAX;

        // Try every value as the range start lo.
        for (auto& row : nums) {
            for (int lo : row) {
                // In each list, find the smallest value >= lo.
                // The range must reach the largest of those values, so hi is that maximum.
                int hi = INT_MIN;
                bool everyListHasOne = true;
                for (auto& other : nums) {
                    auto it = lower_bound(other.begin(), other.end(), lo);
                    if (it == other.end()) { everyListHasOne = false; break; }
                    hi = max(hi, *it);
                }
                if (!everyListHasOne) continue;   // some list has nothing >= lo

                long long width = (long long)hi - lo;
                // Keep the smallest width; on a tie keep the smaller start.
                if (best.empty() || width < bestWidth || (width == bestWidth && lo < best[0])) {
                    bestWidth = width;
                    best = {lo, hi};
                }
            }
        }
        return best;
    }
};

import java.util.Collections;
import java.util.List;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int[] best = new int[0];
        long bestWidth = Long.MAX_VALUE;

        // Try every value as the range start lo.
        for (List<Integer> row : nums) {
            for (int lo : row) {
                // In each list, find the smallest value >= lo.
                // The range must reach the largest of those values, so hi is that maximum.
                int hi = Integer.MIN_VALUE;
                boolean everyListHasOne = true;
                for (List<Integer> other : nums) {
                    int idx = Collections.binarySearch(other, lo);
                    if (idx < 0) {
                        idx = -(idx + 1);
                    }
                    if (idx == other.size()) {
                        everyListHasOne = false;
                        break;
                    }
                    hi = Math.max(hi, other.get(idx));
                }
                if (!everyListHasOne) continue;   // some list has nothing >= lo

                long width = (long) hi - lo;
                // Keep the smallest width; on a tie keep the smaller start.
                if (best.length == 0 || width < bestWidth || (width == bestWidth && lo < best[0])) {
                    bestWidth = width;
                    best = new int[]{lo, hi};
                }
            }
        }
        return best;
    }
}

import bisect
from typing import List

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        best: List[int] = []
        best_width = float("inf")

        # Try every value as the range start lo.
        for row in nums:
            for lo in row:
                # In each list, find the smallest value >= lo.
                # The range must reach the largest of those values, so hi is that maximum.
                hi = -float("inf")
                every_list_has_one = True
                for other in nums:
                    idx = bisect.bisect_left(other, lo)
                    if idx == len(other):
                        every_list_has_one = False
                        break
                    hi = max(hi, other[idx])

                if not every_list_has_one:
                    continue   # some list has nothing >= lo

                width = hi - lo
                # Keep the smallest width; on a tie keep the smaller start.
                if not best or width < best_width or (width == best_width and lo < best[0]):
                    best_width = width
                    best = [lo, int(hi)]

        return best

function lowerBound(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

export function smallestRange(nums: number[][]): number[] {
    let best: number[] = [];
    let bestWidth = Infinity;

    // Try every value as the range start lo.
    for (const row of nums) {
        for (const lo of row) {
            // In each list, find the smallest value >= lo.
            // The range must reach the largest of those values, so hi is that maximum.
            let hi = -Infinity;
            let everyListHasOne = true;
            for (const other of nums) {
                const idx = lowerBound(other, lo);
                if (idx === other.length) {
                    everyListHasOne = false;
                    break;
                }
                hi = Math.max(hi, other[idx]);
            }
            if (!everyListHasOne) continue;   // some list has nothing >= lo

            const width = hi - lo;
            // Keep the smallest width; on a tie keep the smaller start.
            if (best.length === 0 || width < bestWidth || (width === bestWidth && lo < best[0])) {
                bestWidth = width;
                best = [lo, hi];
            }
        }
    }
    return best;
}

Complexity

Time O(N · k log n)Space O(1)

N is the total number of values, k the number of lists and n the length of a list. Each of the N starts needs k binary searches of log n steps each. Starts that sit next to each other repeat most of the same searches.

Better approach

Why brute force is slow

The brute force searches every list again for every start. Each search is a binary search, so the same kind of work is repeated for every value.

What repeated work are we doing?

Starts that sit next to each other on the sorted line need almost the same per-list answers. Brute force still redoes all k searches for each one.

What information can we reuse?

Keep the window as one count per list. Moving the window by one value changes one count, so no list is searched twice.

New approach

Idea

Put every value on one sorted line, and tag each value with its list number. A range is then a window on this line. A window is valid when it holds at least one value from every list. Move the right end forward until the window is valid, then move the left end forward as far as it stays valid. The narrowest valid window is the answer.

Thinking process

1
The brute force searched the lists again for every start. But the starts are just the values, and once I merge them they form one sorted line.
2
On that line, any range is a block of neighbours. So I only need to look at blocks.
3
Keep one count per list: how many of its values are in the window. The window is valid when all k counts are at least 1.
4
Check with real numbers: the window [0, 4, 5] holds 0 from list 1, 4 from list 0 and 5 from list 2. That covers every list, so [0, 5] is valid with width 5. Now move the left end past 0. Since 0 is list 1's only value in the window, the window is no longer valid, so I stop shrinking.
5
So the window grows on the right until it is valid, then shrinks on the left while it stays valid. Each value enters once and leaves once.

Visual

All values sorted, each tagged with its list in the second row. Blue = the window [l, r]; green = the value that just entered on the right; red = the value that just left on the left. A window that holds every list is a candidate range [left value, right value].

Sliding window over the sorted linenums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]step 1/33

values

from list

Setup

values in total: 13
lists in window: 0 / 3

Merge all values into one sorted line, tagged with their list

All 13 values sorted: 0, 4, 5, 9, 10, 12, 15, 18, 20, 22, 24, 26, 30. The second row keeps each value's list, so we can see which lists a window holds.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();

        // Put every value on one line, tagged with the list it came from.
        vector<pair<int, int>> line;            // (value, list)
        for (int i = 0; i < k; i++)
            for (int x : nums[i]) line.push_back({x, i});
        sort(line.begin(), line.end());

        // The window [l .. r] of this line. inWindow[i] = values of list i inside it.
        vector<int> inWindow(k, 0);
        int covered = 0;                        // lists with at least one value in the window
        vector<int> best;
        long long bestWidth = LLONG_MAX;

        int l = 0;
        for (int r = 0; r < (int)line.size(); r++) {
            if (inWindow[line[r].second]++ == 0) covered++;

            // Every list is represented, so [l .. r] is a valid range.
            // Shrink from the left to make it as tight as possible,
            // recording each valid window on the way.
            while (covered == k) {
                int lo = line[l].first, hi = line[r].first;
                long long width = (long long)hi - lo;
                if (best.empty() || width < bestWidth || (width == bestWidth && lo < best[0])) {
                    bestWidth = width;
                    best = {lo, hi};
                }
                if (--inWindow[line[l].second] == 0) covered--;
                l++;
            }
        }
        return best;
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();

        // Put every value on one line, tagged with the list it came from.
        List<int[]> line = new ArrayList<>();   // [value, list]
        for (int i = 0; i < k; i++) {
            for (int x : nums.get(i)) {
                line.add(new int[]{x, i});
            }
        }
        Collections.sort(line, (a, b) -> Integer.compare(a[0], b[0]));

        // The window [l .. r] of this line. inWindow[i] = values of list i inside it.
        int[] inWindow = new int[k];
        int covered = 0;   // lists with at least one value in the window
        int[] best = new int[0];
        long bestWidth = Long.MAX_VALUE;

        int l = 0;
        for (int r = 0; r < line.size(); r++) {
            if (inWindow[line.get(r)[1]]++ == 0) covered++;

            // Every list is represented, so [l .. r] is a valid range.
            // Shrink from the left to make it as tight as possible,
            // recording each valid window on the way.
            while (covered == k) {
                int lo = line.get(l)[0];
                int hi = line.get(r)[0];
                long width = (long) hi - lo;
                if (best.length == 0 || width < bestWidth || (width == bestWidth && lo < best[0])) {
                    bestWidth = width;
                    best = new int[]{lo, hi};
                }
                if (--inWindow[line.get(l)[1]] == 0) covered--;
                l++;
            }
        }
        return best;
    }
}

from typing import List, Tuple

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k = len(nums)

        # Put every value on one line, tagged with the list it came from.
        line: List[Tuple[int, int]] = []   # (value, list)
        for i in range(k):
            for x in nums[i]:
                line.append((x, i))
        line.sort(key=lambda item: item[0])

        # The window [l .. r] of this line. in_window[i] = values of list i inside it.
        in_window = [0] * k
        covered = 0   # lists with at least one value in the window
        best: List[int] = []
        best_width = float("inf")

        l = 0
        for r in range(len(line)):
            if in_window[line[r][1]] == 0:
                covered += 1
            in_window[line[r][1]] += 1

            # Every list is represented, so [l .. r] is a valid range.
            # Shrink from the left to make it as tight as possible,
            # recording each valid window on the way.
            while covered == k:
                lo = line[l][0]
                hi = line[r][0]
                width = hi - lo
                if not best or width < best_width or (width == best_width and lo < best[0]):
                    best_width = width
                    best = [lo, hi]

                in_window[line[l][1]] -= 1
                if in_window[line[l][1]] == 0:
                    covered -= 1
                l += 1

        return best

export function smallestRange(nums: number[][]): number[] {
    const k = nums.length;

    // Put every value on one line, tagged with the list it came from.
    const line: [number, number][] = [];   // [value, list]
    for (let i = 0; i < k; i++) {
        for (const x of nums[i]) {
            line.push([x, i]);
        }
    }
    line.sort((a, b) => a[0] - b[0]);

    // The window [l .. r] of this line. inWindow[i] = values of list i inside it.
    const inWindow = new Array<number>(k).fill(0);
    let covered = 0;   // lists with at least one value in the window
    let best: number[] = [];
    let bestWidth = Infinity;

    let l = 0;
    for (let r = 0; r < line.length; r++) {
        if (inWindow[line[r][1]]++ === 0) covered++;

        // Every list is represented, so [l .. r] is a valid range.
        // Shrink from the left to make it as tight as possible,
        // recording each valid window on the way.
        while (covered === k) {
            const lo = line[l][0];
            const hi = line[r][0];
            const width = hi - lo;
            if (best.length === 0 || width < bestWidth || (width === bestWidth && lo < best[0])) {
                bestWidth = width;
                best = [lo, hi];
            }
            if (--inWindow[line[l][1]] === 0) covered--;
            l++;
        }
    }
    return best;
}

Complexity

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

Sorting the N values costs O(N log N). Each window end moves forward at most N times, so the sliding part is O(N). The per-list counts need O(k) extra space.

Optimized approach

Idea

Start from brute force

Brute force tries each value as the start and binary searches every list again for each start.

Find the repeated work

Two neighbouring starts need almost the same per-list answers. Brute force rebuilds all of them from scratch for every start.

Define the state — what variables do I need?

heap: Exactly one value from each list: that list's current value. Its top is the smallest of them.
curMax: The largest value currently in the heap. It never goes down, because each new value is pushed in.
best: The narrowest `[heap top, curMax]` range seen so far.

Define validity

The range [heap top, curMax] is valid because the heap holds exactly one value from every list, so every list has a value between the smallest and the largest.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Push the first value of every list; set curMax to the largest of them

Each list has to give one value to start with, and its first value is the smallest it can offer.

Every step

Record `[heap top, curMax]` if it is narrower than best; then pop the heap top

Popping the smallest value is the only move that can raise the start. Moving any other list cannot make the range narrower.

The popped value was the last one in its list

Stop

Every range that comes later needs a value from this list, and none are left.

Otherwise, after the pop

Push the next value of that list, then set curMax = max(curMax, that value)

The new value may now be the largest, so curMax has to include it. The heap still holds exactly one value per list.

What does the current window add to the answer?

Each step gives one candidate, [heap top, curMax]. Every candidate is valid, and the narrowest of them is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();

        // Min-heap of (value, list, column). It holds exactly one value from each list.
        using Item = tuple<int, int, int>;
        priority_queue<Item, vector<Item>, greater<Item>> heap;
        int curMax = INT_MIN;                   // largest value currently in the heap
        for (int i = 0; i < k; i++) {
            heap.push({nums[i][0], i, 0});
            curMax = max(curMax, nums[i][0]);
        }

        vector<int> best;
        long long bestWidth = LLONG_MAX;
        while (true) {
            // Top = smallest value in the heap, curMax = largest.
            // Together they cover one value from every list.
            auto [lo, row, col] = heap.top();
            long long width = (long long)curMax - lo;
            // Strict <: the heap top never goes down, so the first range of a
            // given width is the one with the smallest start.
            if (width < bestWidth) {
                bestWidth = width;
                best = {lo, curMax};
            }

            // Drop the smallest value and bring in the next value from the same list.
            heap.pop();
            if (col + 1 == (int)nums[row].size()) break;   // this list is used up: stop
            int nxt = nums[row][col + 1];
            heap.push({nxt, row, col + 1});
            curMax = max(curMax, nxt);
        }
        return best;
    }
};

import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();

        // Min-heap of [value, list, column]. It holds exactly one value from each list.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int curMax = Integer.MIN_VALUE;   // largest value currently in the heap
        for (int i = 0; i < k; i++) {
            int val = nums.get(i).get(0);
            heap.offer(new int[]{val, i, 0});
            curMax = Math.max(curMax, val);
        }

        int[] best = new int[0];
        long bestWidth = Long.MAX_VALUE;
        while (true) {
            // Top = smallest value in the heap, curMax = largest.
            // Together they cover one value from every list.
            int[] top = heap.poll();
            int lo = top[0];
            int row = top[1];
            int col = top[2];

            long width = (long) curMax - lo;
            // Strict <: the heap top never goes down, so the first range of a
            // given width is the one with the smallest start.
            if (width < bestWidth) {
                bestWidth = width;
                best = new int[]{lo, curMax};
            }

            // Drop the smallest value and bring in the next value from the same list.
            if (col + 1 == nums.get(row).size()) break;   // this list is used up: stop
            int nxt = nums.get(row).get(col + 1);
            heap.offer(new int[]{nxt, row, col + 1});
            curMax = Math.max(curMax, nxt);
        }
        return best;
    }
}

import heapq
from typing import List, Tuple

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k = len(nums)

        # Min-heap of (value, list, column). It holds exactly one value from each list.
        heap: List[Tuple[int, int, int]] = []
        cur_max = -float("inf")   # largest value currently in the heap
        for i in range(k):
            val = nums[i][0]
            heapq.heappush(heap, (val, i, 0))
            cur_max = max(cur_max, val)

        best: List[int] = []
        best_width = float("inf")
        while True:
            # Top = smallest value in the heap, cur_max = largest.
            # Together they cover one value from every list.
            lo, row, col = heapq.heappop(heap)
            width = cur_max - lo
            # Strict <: the heap top never goes down, so the first range of a
            # given width is the one with the smallest start.
            if width < best_width:
                best_width = width
                best = [lo, int(cur_max)]

            # Drop the smallest value and bring in the next value from the same list.
            if col + 1 == len(nums[row]):
                break   # this list is used up: stop
            nxt = nums[row][col + 1]
            heapq.heappush(heap, (nxt, row, col + 1))
            cur_max = max(cur_max, nxt)

        return best

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function smallestRange(nums: number[][]): number[] {
    const k = nums.length;

    // Min-heap of [value, list, column]. It holds exactly one value from each list.
    const heap = new PriorityQueue<[number, number, number]>((a, b) => a[0] - b[0]);
    let curMax = -Infinity;   // largest value currently in the heap
    for (let i = 0; i < k; i++) {
        heap.push([nums[i][0], i, 0]);
        curMax = Math.max(curMax, nums[i][0]);
    }

    let best: number[] = [];
    let bestWidth = Infinity;
    while (true) {
        // Top = smallest value in the heap, curMax = largest.
        // Together they cover one value from every list.
        const [lo, row, col] = heap.pop()!;
        const width = curMax - lo;
        // Strict <: the heap top never goes down, so the first range of a
        // given width is the one with the smallest start.
        if (width < bestWidth) {
            bestWidth = width;
            best = [lo, curMax];
        }

        // Drop the smallest value and bring in the next value from the same list.
        if (col + 1 === nums[row].length) break;   // this list is used up: stop
        const nxt = nums[row][col + 1];
        heap.push([nxt, row, col + 1]);
        curMax = Math.max(curMax, nxt);
    }
    return best;
}

Complexity

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

Each of the N values enters the heap once and leaves once. The heap never holds more than k values, so each operation costs O(log k). Nothing needs to be sorted again, since each list is already sorted.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each value lo, binary search every list for its first value ≥ lo; keep the narrowest range	O(N · k log n)	O(1)
Better	Merge every value onto one sorted line, then slide a window that must hold a value from every list	O(N log N)	O(N)
Optimal	Keep one value per list in a min-heap and track the largest; the range is [heap top, largest]	O(N log k)	O(k)

Why does this belong to this pattern?

Clues in the problem statement

“smallest range”A start and an end judged by width: the minimum-width window that touches many lists.
“at least one number from every list”Every list must be represented, so keep one candidate per list at a time.
“sorted lists”Each list's next value is its next bigger one, so each candidate can move forward on its own.

K sorted lists+range must touch every list+one candidate per list in a min-heap + running max→K-way Merge — Smallest range (min-heap with one value per list, plus curMax)

Merge K Sorted Lists also keeps a heap of one value per list, but it has to output every value, so it runs until all lists are empty. This question asks for a range, so the heap keeps one value per list, the end is a running curMax, and the answer is [heap top, curMax]. The stop rule is different too: this question stops as soon as one list runs out, because no later range can touch that list.

Don't make this mistake

Forgetting to update curMax when a value is pushed

✗ heap.push({nums[row][col + 1], row, col + 1}); // curMax is not touched

✓ heap.push({nums[row][col + 1], row, col + 1}); curMax = max(curMax, nums[row][col + 1]);

On the dry run, curMax stays 5 forever. After the first pop (0 from list 1), the code records [4, 5], which has no value from list 1 at all, because its next value is 9. The final answer comes out as [20, 5], a range that ends before it starts.

Pattern confusion: running until every list is empty

✗ while (!heap.empty()) { auto [v, row, col] = heap.top(); heap.pop(); if (col + 1 < (int)nums[row].size()) { heap.push({nums[row][col + 1], row, col + 1}); curMax = max(curMax, nums[row][col + 1]); } }

✓ if (col + 1 == (int)nums[row].size()) break; // a list is used up: stop here

Merge K Sorted Lists keeps going until every list is empty, because it has to output every value. This problem needs a value from every list, so once one list is used up, no later range can cover it. On the dry run, popping 20 (the last value of list 1) leaves only 22 and 24 in the heap, and the wrong code records [22, 24], which has no value from list 1. It keeps going and ends at [30, 30], which has no value from list 0.

Using <= in the width check

✗ if (width <= bestWidth) { bestWidth = width; best = {lo, curMax}; }

✓ if (width < bestWidth) { bestWidth = width; best = {lo, curMax}; }

On [[1, 5], [2, 6]], the range [1, 2] has width 1, and so does [5, 6]. The heap top only goes up, so [5, 6] is found later and has the larger start. With <= it replaces [1, 2], and the code returns [5, 6]. The tie rule keeps [1, 2].

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture