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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Sorting, Greedy, Heap, Sliding Window
- Asked at: Amazon, Google, PhonePe, 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 == k1 <= k <= 35001 <= nums[i].length <= 50-10^5 <= nums[i][j] <= 10^5nums[i] is sorted in non-decreasing order.
Hints for Smallest Range Covering Elements from K Lists
Hint 1
Tag every number with the list it came from and merge them all into one sorted sequence.
Hint 2
Then you need the shortest window of that sequence containing all
ktags.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
- 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]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