Smallest Range Covering Elements from K Lists — Hard Problem & Solution

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.

Difficulty: Hard
Topics: Arrays, Hash Table, Greedy, Sorting, Sliding Window, Heap
Asked at: Amazon, Google, LinkedIn
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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.

Range [a, b] is smaller than [c, d] if b - a < d - c, or if the widths tie and a < c.

Example 1

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 24 from the first list, 20 from the second, 22 from the third.

Example 2

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
Explanation: The single value 1 appears in every list.

Example 3

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

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.

How to solve Smallest Range Covering Elements from K Lists

Flatten the lists into (value, listIndex) pairs sorted by value, then find the shortest window covering all k list indices with a sliding window.

Approach

Build the tagged pairs and sort by value, breaking ties by list index.
Extend the right edge, incrementing that list's count and the covered tally when it first appears.
While every list is covered, record the window and shrink from the left.
Return the best window seen.

Why it works

Shrinking greedily while the window is still valid is what finds the shortest range ending at each right edge — the same reason the strict < comparison also delivers the tie-break: the first window of a given width encountered has the smallest a, since lo only moves forward. The classic alternative keeps one pointer per list in a min-heap; both are the same sweep seen from different angles.

Complexity

Time — O(N log N) with N the total number of values
Space — O(N)

Pitfalls

The tally counts lists covered, not values in the window.
Shrink while the window is valid, then record — recording after the shrink misses the best window.
Duplicated values across lists must each keep their own tag.

Reference solution

Python

from typing import List

def smallestRange(nums: List[List[int]]) -> List[int]:
    k = len(nums)
    items = [(v, i) for i in range(k) for v in nums[i]]
    items.sort()
    count = [0] * k
    have = 0
    lo = 0
    found = False
    best_a = best_b = 0
    for hi in range(len(items)):
        if count[items[hi][1]] == 0:
            have += 1
        count[items[hi][1]] += 1
        while have == k:
            if not found or items[hi][0] - items[lo][0] < best_b - best_a:
                found = True
                best_a, best_b = items[lo][0], items[hi][0]
            count[items[lo][1]] -= 1
            if count[items[lo][1]] == 0:
                have -= 1
            lo += 1
    return [best_a, best_b]

JavaScript

var smallestRange = function(nums) {
    var k = nums.length, i, j;
    var items = [];
    for (i = 0; i < k; i++) {
        for (j = 0; j < nums[i].length; j++) items.push([nums[i][j], i]);
    }
    items.sort(function(a, b) { return (a[0] - b[0]) || (a[1] - b[1]); });
    var count = [];
    for (i = 0; i < k; i++) count.push(0);
    var have = 0, lo = 0;
    var found = false, bestA = 0, bestB = 0;
    for (var hi = 0; hi < items.length; hi++) {
        if (count[items[hi][1]] === 0) have++;
        count[items[hi][1]]++;
        while (have === k) {
            if (!found || items[hi][0] - items[lo][0] < bestB - bestA) {
                found = true;
                bestA = items[lo][0];
                bestB = items[hi][0];
            }
            count[items[lo][1]]--;
            if (count[items[lo][1]] === 0) have--;
            lo++;
        }
    }
    return [bestA, bestB];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue