#632 Smallest Range Covering Elements from K Lists
the problem
In plain words
You get 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 when b − a is smaller; when two ranges are equally wide, the one with the smaller a wins.
in nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
out [20,24]
24 from the first list, 20 from the second and 22 from the third all lie in [20, 24].
in nums = [[1,2,3],[1,2,3],[1,2,3]]
out [1,1]
- k == nums.size(), 1 ≤ k ≤ 3500
- 1 ≤ nums[i].size() ≤ 50
- -10⁵ ≤ nums[i][j] ≤ 10⁵
- Each list is sorted in non-decreasing order
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternK-way mergeSliding window (variable size)
Pick one number from each list: your range is [smallest pick, largest pick]. The only move that can shrink it is raising the smallest pick to the next number of its list. A min-heap finds the smallest pick; a variable remembers the largest.
solutions
From brute force to optimal
The best range starts at some element a; for each a, every list contributes its first element ≥ a, and b is the largest of those.
- Collect the distinct values in a TreeSet (ascending).
- For each a, binary-search every list for its first element ≥ a; b = the largest of them.
- If some list has nothing ≥ a, stop — bigger starts fail too.
- Keep the smallest [a, b]; ascending order makes ties keep the smaller a.
N candidate starts × k lists × a binary search in a list of length L ≤ 50 — billions of steps at the limits.
The set of candidate starts.
class Solution { public int[] smallestRange(List<List<Integer>> nums) { TreeSet<Integer> starts = new TreeSet<>(); // the best range always starts at some element for (List<Integer> list : nums) starts.addAll(list); int bestLo = 0, bestHi = -1; // hi < lo means "nothing found yet" for (int a : starts) { // ascending, so ties keep the smaller start int b = a; for (List<Integer> list : nums) { int i = lowerBound(list, a); // this list's first element ≥ a if (i == list.size()) return new int[] {bestLo, bestHi}; // nothing ≥ a: bigger starts fail too b = Math.max(b, list.get(i)); } if (bestHi < bestLo || b - a < bestHi - bestLo) { bestLo = a; bestHi = b; } } return new int[] {bestLo, bestHi}; } private static int lowerBound(List<Integer> list, int target) { int lo = 0, hi = list.size(); while (lo < hi) { int mid = (lo + hi) >>> 1; if (list.get(mid) < target) lo = mid + 1; else hi = mid; } return lo; }}Keep each list's current element in a min-heap and track the maximum; record [min, max], then advance the list that holds the min.
- Offer each list's first element as {value, list, index}; max = the largest of them.
- The current range is [heap min, max]; record it if strictly smaller.
- Poll the min and offer the next element of its list, updating max.
- Stop as soon as a list runs out — no later range can include it.
Each of the N elements is offered and polled at most once on a heap of size k.
One entry per list.
class Solution { public int[] smallestRange(List<List<Integer>> nums) { // entry {value, list, index}: the current element of each list; smallest value on top PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0])); int max = Integer.MIN_VALUE; // largest current element for (int r = 0; r < nums.size(); r++) { int v = nums.get(r).get(0); heap.offer(new int[] {v, r, 0}); max = Math.max(max, v); } int bestLo = heap.peek()[0], bestHi = max; while (true) { int[] min = heap.poll(); // right now the range is [min, max] if (max - min[0] < bestHi - bestLo) { // strictly smaller: ties keep the smaller start bestLo = min[0]; bestHi = max; } int r = min[1], i = min[2] + 1; if (i == nums.get(r).size()) break; // a list ran out: no later range covers it int v = nums.get(r).get(i); heap.offer(new int[] {v, r, i}); // move that list's pointer forward max = Math.max(max, v); } return new int[] {bestLo, bestHi}; }}Tag every value with its list id, sort, and find the narrowest window that contains all k ids.
- Build (value, list) pairs and sort by value.
- Grow the right end until all k lists are inside.
- Shrink the left end while they still are, recording each window.
The sort dominates; the window itself is O(N).
All tagged values.
class Solution { public int[] smallestRange(List<List<Integer>> nums) { List<int[]> all = new ArrayList<>(); // {value, list} for (int r = 0; r < nums.size(); r++) for (int v : nums.get(r)) all.add(new int[] {v, r}); all.sort(Comparator.comparingInt(e -> e[0])); int k = nums.size(), covered = 0; int bestLo = all.get(0)[0], bestHi = all.get(all.size() - 1)[0]; // everything always covers int[] inWindow = new int[k]; // elements of each list inside the window for (int left = 0, right = 0; right < all.size(); right++) { if (inWindow[all.get(right)[1]]++ == 0) covered++; while (covered == k) { // every list is inside: try to shrink int lo = all.get(left)[0], hi = all.get(right)[0]; if (hi - lo < bestHi - bestLo) { bestLo = lo; bestHi = hi; } if (--inWindow[all.get(left)[1]] == 0) covered--; left++; } } return new int[] {bestLo, bestHi}; }}in the room
How to say it in the interview
talk track
- Say the key observation: with one pick per list, only raising the minimum pick can shrink the range.
- Then: min-heap for the minimum, a variable for the maximum — it's merge k sorted lists that stops when any list runs out.
- Offer the sort + sliding-window version as a second solution ("the minimum window that contains all k colours").
traps
- Continuing after a list runs out — every later range misses that list.
- Updating the best range with ≤ instead of < — ties must keep the smaller start, which you found first.
- Forgetting to update max when a new value enters the heap.
what they ask next
Follow-ups
Why can't moving any other pointer help?
Raising a pick that isn't the minimum leaves the minimum where it is and can only raise the maximum, so the width can't drop.
How does it relate to Minimum Window Substring (LC 76)?
The sort + slide version is exactly a minimum window that must contain all k "colours" (list ids).
before you submit
Edge cases to test
- k = 1: the answer is [first value, first value].
- Equal widths: [1, 3] and [3, 5] are both width 2 — the smaller start, [1, 3], wins.
- Duplicates inside a list, and values at ±10⁵ (a width up to 2·10⁵ fits easily in an int).
- A list with a single element: every candidate range must include it.
practise next
Similar problems
- #23Merge k Sorted ListsHardin Heaps
- #76Minimum Window SubstringHardin Sliding Window
- #373Find K Pairs with Smallest SumsMediumin Heaps