Smallest Range Covering Elements From K Lists
You are given k lists of whole numbers, and every list is already sorted from smallest to largest. Find the smallest range [a, b] that contains at least one number from every list. A range [a, b] is smaller than [c, d] when b - a is smaller than d - c. If two ranges are the same width, the one starting earlier wins. Keep a pointer into each list , all starting at position 0, and hold the k numbers those pointers sit on in a min-heap. Those k numbers already touch every list, so the range from the smallest of them to the largest of them is a valid answer. Record it, then move the pointer that produced the smallest number forward by one and try again. When any list runs out, no better range can exist.
Constraints
- 1 ≤ nums.length ≤ 3500
- 1 ≤ numsi.length ≤ 50
- Each numsi is sorted from smallest to largest
- -105 ≤ numsi[j] ≤ 105
Example
Input
nums = [[1, 9], [8, 12], [6, 7]]Output
[7, 9]Explanation The range from 7 to 9 contains 9 from the first list, 8 from the second list and 7 from the third list, and it is only 2 wide. No narrower range covers all three lists.
In plain terms
- Heap
- A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
- Backing array
- A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
- Min-heap
- A heap whose best item is the smallest one. Each item here is a number together with which list it came from and where in that list it sits.
- Pointer into a list
- A position number saying how far you have walked into that list. Moving a pointer forward means looking at the next, larger, number in the same list.
- Why the largest is tracked separately
- A min-heap only tells you its smallest item cheaply. The largest of the k current numbers is kept in its own variable, updated whenever a bigger number is pushed in, because numbers only ever grow as pointers move forward.
The row of boxes is the backing array of the min-heap, holding the number each list pointer is currently on
01
18
26
Statusinit
Push the first number of each list. The heap holds 1, 8 and 6.
What happens in this step
pointers all at position 0 backing array = [1, 8, 6] highest = 8 best range so far = [1, 8], width 7 Slot 0 holds 1, the smallest of the three. These three numbers already cover all three lists, so [1, 8] is a valid starting answer.
Step 1 of 5
Steps to visualize
- The lists are list 0 = [1, 9], list 1 = [8, 12] and list 2 = [6, 7].
- Each box is one slot of the list that stores the heap. There is always exactly one number per input list, so the heap stays 3 items wide.
- The largest of the three numbers is tracked in a separate variable called highest.
- Each round: pop the smallest, compare highest minus that smallest against the best range so far, then push the next number from the same list.
- The moment a list has no next number, the search stops.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
01
18
26
Statusinit
Push the first number of each list. The heap holds 1, 8 and 6.
What happens in this step
pointers all at position 0 backing array = [1, 8, 6] highest = 8 best range so far = [1, 8], width 7 Slot 0 holds 1, the smallest of the three. These three numbers already cover all three lists, so [1, 8] is a valid starting answer.
Step 1 of 5
Solution
function smallestRange(nums) {
const heap = new Heap((a, b) => a[0] - b[0]);
let highest = -Infinity;
for (let list = 0; list < nums.length; list++) {
heap.push([nums[list][0], list, 0]);
highest = Math.max(highest, nums[list][0]);
}
let start = heap.peek()[0];
let end = highest;
while (true) {
const smallest = heap.pop();
if (highest - smallest[0] < end - start) {
start = smallest[0];
end = highest;
}
const nextIndex = smallest[2] + 1;
if (nextIndex === nums[smallest[1]].length) return [start, end];
const nextValue = nums[smallest[1]][nextIndex];
highest = Math.max(highest, nextValue);
heap.push([nextValue, smallest[1], nextIndex]);
}
}
class Heap {
constructor(compare) {
this.items = [];
this.compare = compare;
}
size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(value) {
this.items.push(value);
let child = this.items.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (this.compare(this.items[child], this.items[parent]) >= 0) break;
const swap = this.items[child];
this.items[child] = this.items[parent];
this.items[parent] = swap;
child = parent;
}
}
pop() {
const top = this.items[0];
const last = this.items.pop();
if (this.items.length > 0) {
this.items[0] = last;
let parent = 0;
while (true) {
const left = parent * 2 + 1;
const right = parent * 2 + 2;
let best = parent;
if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
if (best === parent) break;
const swap = this.items[parent];
this.items[parent] = this.items[best];
this.items[best] = swap;
parent = best;
}
}
return top;
}
}- Time
- O(n log k) where n is the total count of numbers and k is the number of lists
- Space
- O(k)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [[1, 9], [8, 12], [6, 7]] | [7, 9] | example from the docstring |
nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]] | [20, 24] | larger lists where the answer sits in the middle |
nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]] | [1, 1] | duplicate values across lists give a range of width zero |
nums = [[1], [2], [3]] | [1, 3] | every list runs out immediately, so the first range is the answer |
nums = [[1, 2, 3, 4, 5]] | [1, 1] | degenerate case with a single list |
nums = [[-5, -2, 0], [-1, 3], [2, 4]] | [-1, 2] | negative values mixed with positive ones |