Smallest Range Covering Elements from K Lists

Hard
977.

Smallest Range Covering Elements from K Lists

Smallest Range Covering Elements from K Lists is a hard coding problem on arrays, hash table and sorting, asked in Amazon, Google, PhonePe and LinkedIn interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var smallestRange = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Range Covering Elements from K Lists — Solution

Smallest Range Covering Elements from K Lists solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest Range Covering Elements from K Lists is a hard coding problem on arrays, hash table and sorting, asked in Amazon, Google, PhonePe and LinkedIn interviews.

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.

Hints for Smallest Range Covering Elements from K Lists

  1. Hint 1

    Tag every number with the list it came from and merge them all into one sorted sequence.

  2. Hint 2

    Then you need the shortest window of that sequence containing all k tags.

  3. Hint 3

    That is a sliding window with a per-list count and a "how many lists are covered" tally.

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

  1. Build the tagged pairs and sort by value, breaking ties by list index.
  2. Extend the right edge, incrementing that list's count and the covered tally when it first appears.
  3. While every list is covered, record the window and shrink from the left.
  4. 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]

Java

public static int[] smallestRange(int[][] nums) {
    int k = nums.length;
    List<int[]> items = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        for (int v : nums[i]) items.add(new int[] { v, i });
    }
    items.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    int[] count = new int[k];
    int have = 0, lo = 0;
    boolean found = false;
    int bestA = 0, bestB = 0;
    for (int hi = 0; hi < items.size(); hi++) {
        int[] cur = items.get(hi);
        if (count[cur[1]] == 0) have++;
        count[cur[1]]++;
        while (have == k) {
            int[] left = items.get(lo);
            if (!found || cur[0] - left[0] < bestB - bestA) {
                found = true;
                bestA = left[0];
                bestB = cur[0];
            }
            count[left[1]]--;
            if (count[left[1]] == 0) have--;
            lo++;
        }
    }
    return new int[] { bestA, bestB };
}

C++

vector<int> smallestRange(vector<vector<int>>& nums) {
    int k = (int) nums.size();
    vector<pair<int,int>> items;
    for (int i = 0; i < k; i++) {
        for (int v : nums[i]) items.push_back({ v, i });
    }
    sort(items.begin(), items.end());
    vector<int> count(k, 0);
    int have = 0, lo = 0;
    bool found = false;
    int bestA = 0, bestB = 0;
    for (size_t hi = 0; hi < items.size(); hi++) {
        if (count[items[hi].second] == 0) have++;
        count[items[hi].second]++;
        while (have == k) {
            if (!found || items[hi].first - items[lo].first < bestB - bestA) {
                found = true;
                bestA = items[lo].first;
                bestB = items[hi].first;
            }
            count[items[lo].second]--;
            if (count[items[lo].second] == 0) have--;
            lo++;
        }
    }
    return { bestA, bestB };
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets