DSA-074 · FOCUSED PRACTICE
Smallest Range Covering K Sorted Lists
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 3741 deterministic checks. Learner drafts are not executed.
Understand the problem
Find the smallest inclusive numeric range containing at least one value from every sorted input list. Return a fresh [start,end] pair, minimizing width and then start value.
- lists is nonnull with 1..10,000 nonnull, nonempty rows and at most 100,000 total values. Each row is nondecreasing; sortedness and size bounds are preconditions. Empty outer/inner rows throw IllegalArgumentException; null outer array throws NullPointerException.
- Values span the full int domain. Compare widths in long because MAX−MIN is 4,294,967,295. Among equal widths choose the smaller start; a single list therefore returns [its first value,its first value].
- Return a fresh two-int array, with no mutation of cells or row references. Duplicates and shared input row objects are allowed. The optimized frontier carries one occurrence from every source; after polling, the held minimum plus the remaining heap form the candidate coverage set.
Examples
Input:
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output:[20,24]It covers 24 from source 0, 20 from source 1, and 22 from source 2; narrower candidates cannot cover all three.
Input:
[[1,4],[2,5]]
Output:[1,2][4,5] has the same width one, so the smaller start wins.
Input:
[[MIN],[MAX]]
Output:[MIN,MAX]This valid range has width above int capacity and exhausts a source immediately.
Before you start
- K-way heap frontiers (DSA-072)
- Inclusive ranges, long widths, and deterministic optimization ties
Recognize the structure
A feasible candidate needs coverage of all sources, not just adjacent values in a global sort. A heap maintains the smallest current witness while a scalar maximum gives the right endpoint. Advancing the minimum is the only frontier change that can raise the left endpoint instead of merely worsening the right.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 130/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Keep one current witness from each sorted list.
Hint 2
The smallest witness limits the left endpoint; keep the largest in a scalar.
Hint 3
Evaluate [held minimum,current maximum], then advance only that minimum’s source or stop if it is exhausted.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Flatten labelled values, then slide a coverage window
Sort all (value,source) occurrences globally. Grow a right boundary while tracking source counts, then shrink left while every source is covered, recording width/start rank. For [[1,4],[2,5]], labelled order is 1₀,2₁,4₀,5₁; windows [1,2] and [4,5] both have width one, with [1,2] preferred. This O(N log(N+1)) method uses O(N+k) storage and provides an independent algorithmic baseline.
Improve the baseline
Initialize a covered frontier
Queue the first element of every list and set maximum to their greatest value. These k witnesses define a valid inclusive candidate even with duplicate values.
Evaluate before losing coverage
Poll the smallest witness into a local minimum record. That held record plus the remaining heap still defines [minimum.value,maximum]. Update the best using long width and then smaller-start comparison.
Advance the limiting source
If the minimum’s source has a successor, queue it and update maximum. Otherwise stop: future covered frontiers cannot be built, and all useful ranges starting no later than that exhausted minimum have already been dominated or evaluated.
Why it is correct
Coverage and maximum invariant
At each complete frontier there is exactly one current occurrence from every list. maximum equals their maximum: replacing the minimum by a nondecreasing successor cannot lower the previous maximum. A polled/held witness remains part of the candidate until replacement or termination.
Why advancing the minimum is sufficient
Changing another witness cannot increase the current minimum and can only preserve or increase the maximum, so it cannot improve the current range. Discard the limiting occurrence only after evaluating its candidate and advance its own source.
Optimal-range coverage argument
Consider any feasible [L,R]. Every source has an occurrence within it. As the algorithm advances smaller frontier values, it cannot exhaust a source before reaching its first value >=L, since that source has a witness in [L,R]. When all frontier values first reach >=L, each chosen value is its source’s first such witness and is <=R. That candidate lies within [L,R], so an optimum is encountered or improved upon. Width/start tie comparison preserves the preferred optimum.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
public final class Solution {
private record Entry(int value, int source, int index) {}
private static final Comparator<Entry> ORDER = Comparator.comparingInt(Entry::value).thenComparingInt(Entry::source).thenComparingInt(Entry::index);
private static void validate(int[][] lists) {
Objects.requireNonNull(lists, "lists");
if (lists.length == 0) throw new IllegalArgumentException("no lists");
for (int[] row : lists) if (row == null || row.length == 0) throw new IllegalArgumentException("empty list");
}
private static boolean better(int lo, int hi, int bestLo, int bestHi) {
long width = (long) hi - lo, bestWidth = (long) bestHi - bestLo;
return width < bestWidth || width == bestWidth && lo < bestLo;
}
public static int[] smallestRange(int[][] lists) {
validate(lists);
PriorityQueue<Entry> current = new PriorityQueue<>(ORDER);
int maximum = Integer.MIN_VALUE;
for (int i = 0; i < lists.length; i++) {
current.offer(new Entry(lists[i][0],i,0));
maximum = Math.max(maximum,lists[i][0]);
}
int bestLo = current.peek().value, bestHi = maximum;
while (true) {
Entry minimum = current.poll();
if (better(minimum.value,maximum,bestLo,bestHi)) { bestLo = minimum.value; bestHi = maximum; }
int next = minimum.index + 1;
if (next == lists[minimum.source].length) break;
int value = lists[minimum.source][next];
current.offer(new Entry(value,minimum.source,next));
maximum = Math.max(maximum,value);
}
return new int[]{bestLo,bestHi};
}
public static int[] baseline(int[][] lists) {
validate(lists);
ArrayList<Entry> all = new ArrayList<>();
for (int s = 0; s < lists.length; s++) for (int i = 0; i < lists[s].length; i++) all.add(new Entry(lists[s][i],s,i));
all.sort(ORDER);
int[] counts = new int[lists.length];
int covered = 0, left = 0, bestLo = all.get(0).value, bestHi = all.get(all.size()-1).value;
for (int right = 0; right < all.size(); right++) {
if (counts[all.get(right).source]++ == 0) covered++;
while (covered == lists.length) {
int lo = all.get(left).value, hi = all.get(right).value;
if (better(lo,hi,bestLo,bestHi)) { bestLo = lo; bestHi = hi; }
if (--counts[all.get(left++).source] == 0) covered--;
}
}
return new int[]{bestLo,bestHi};
}
}
Read the meaningful blocks
Carry source and occurrence index
Value ties alone do not identify which list to advance. source/index metadata makes successor selection exact.
Widen endpoint subtraction
Cast before hi−lo. Both range comparisons use long width and ordinary safe int start comparison.
Stop on first exhausted minimum
After evaluating the candidate, no successor means coverage cannot be maintained by this frontier. Do not continue with k−1 sources or silently ignore an empty list.
Complexity
Validation and heap initialization cost O(k log(k+1)); at most N extractions/advances give O(N log(k+1)) total for nonempty sources. Auxiliary frontier storage is O(k), and the returned range is constant-sized output.
The flatten/window baseline costs O(N log(N+1)) time and O(N+k) storage. A literal brute-force combination of one witness per list can be exponential and is used only as a small-test conceptual oracle, not the implementation.
Exact-state walkthroughs
Reveal normal and boundary traces
Covered frontier follows the limiting source
Input: [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] · Inclusive covering range: [20,24]
Step 1 of 20: Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
Phase: initial. Current maximum: 5. Best inclusive range: [0, 5], long width 5.
Complete candidate frontier — one occurrence per source
- source 1, index 0: 0 (queued)
- source 0, index 0: 4 (queued)
- source 2, index 0: 5 (queued)
Actual heap after any poll — minimum priority first
- source 1: 0
- source 0: 4
- source 2: 5
The held record remains part of coverage after poll; the heap alone may contain only k−1 sources. Stop only after evaluating the exhausted source’s last valid candidate.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lists | [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] |
| positions | [0,0,0] |
| heap | [{"value":0,"source":1,"index":0},{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}] |
| held | null |
| frontier | [{"value":0,"source":1,"index":0},{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}] |
| maximum | 5 |
| best | [0,5] |
| bestWidth | 5 |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.PriorityQueue; 5 public final class Solution { 6 private record Entry(int value, int source, int index) {} 7 private static final Comparator<Entry> ORDER = Comparator.comparingInt(Entry::value).thenComparingInt(Entry::source).thenComparingInt(Entry::index); 8 private static void validate(int[][] lists) { 9 Objects.requireNonNull(lists, "lists"); 10 if (lists.length == 0) throw new IllegalArgumentException("no lists"); 11 for (int[] row : lists) if (row == null || row.length == 0) throw new IllegalArgumentException("empty list"); 12 } 13 private static boolean better(int lo, int hi, int bestLo, int bestHi) { 14 long width = (long) hi - lo, bestWidth = (long) bestHi - bestLo; 15 return width < bestWidth || width == bestWidth && lo < bestLo; 16 } 17 public static int[] smallestRange(int[][] lists) { 18 validate(lists); 19 PriorityQueue<Entry> current = new PriorityQueue<>(ORDER); 20 int maximum = Integer.MIN_VALUE; 21 for (int i = 0; i < lists.length; i++) { 22 current.offer(new Entry(lists[i][0],i,0)); 23 maximum = Math.max(maximum,lists[i][0]); 24 } 25 int bestLo = current.peek().value, bestHi = maximum; 26 while (true) { 27 Entry minimum = current.poll(); 28 if (better(minimum.value,maximum,bestLo,bestHi)) { bestLo = minimum.value; bestHi = maximum; } 29 int next = minimum.index + 1; 30 if (next == lists[minimum.source].length) break; 31 int value = lists[minimum.source][next]; 32 current.offer(new Entry(value,minimum.source,next)); 33 maximum = Math.max(maximum,value); 34 } 35 return new int[]{bestLo,bestHi}; 36 } 37 public static int[] baseline(int[][] lists) { 38 validate(lists); 39 ArrayList<Entry> all = new ArrayList<>(); 40 for (int s = 0; s < lists.length; s++) for (int i = 0; i < lists[s].length; i++) all.add(new Entry(lists[s][i],s,i)); 41 all.sort(ORDER); 42 int[] counts = new int[lists.length]; 43 int covered = 0, left = 0, bestLo = all.get(0).value, bestHi = all.get(all.size()-1).value; 44 for (int right = 0; right < all.size(); right++) { 45 if (counts[all.get(right).source]++ == 0) covered++; 46 while (covered == lists.length) { 47 int lo = all.get(left).value, hi = all.get(right).value; 48 if (better(lo,hi,bestLo,bestHi)) { bestLo = lo; bestHi = hi; } 49 if (--counts[all.get(left++).source] == 0) covered--; 50 } 51 } 52 return new int[]{bestLo,bestHi}; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[0,0,0]- heap
[{"value":0,"source":1,"index":0},{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}]- held
null- frontier
[{"value":0,"source":1,"index":0},{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}]- maximum
5- best
[0,5]- bestWidth
5- phase
"initial"
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[0,0,0]- heap
[{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}]- held
{"value":0,"source":1,"index":0}- frontier
[{"value":0,"source":1,"index":0},{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0}]- maximum
5- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[0,5]- width
5- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[0,1,0]- heap
[{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1}]- held
null- frontier
[{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1}]- maximum
9- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":9,"source":1,"index":1}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[0,1,0]- heap
[{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1}]- held
{"value":4,"source":0,"index":0}- frontier
[{"value":4,"source":0,"index":0},{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1}]- maximum
9- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[4,9]- width
5- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,1,0]- heap
[{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1}]- held
null- frontier
[{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1}]- maximum
10- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":10,"source":0,"index":1}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,1,0]- heap
[{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1}]- held
{"value":5,"source":2,"index":0}- frontier
[{"value":5,"source":2,"index":0},{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1}]- maximum
10- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[5,10]- width
5- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,1,1]- heap
[{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1},{"value":18,"source":2,"index":1}]- held
null- frontier
[{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":18,"source":2,"index":1}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,1,1]- heap
[{"value":10,"source":0,"index":1},{"value":18,"source":2,"index":1}]- held
{"value":9,"source":1,"index":1}- frontier
[{"value":9,"source":1,"index":1},{"value":10,"source":0,"index":1},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[9,18]- width
9- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,2,1]- heap
[{"value":10,"source":0,"index":1},{"value":12,"source":1,"index":2},{"value":18,"source":2,"index":1}]- held
null- frontier
[{"value":10,"source":0,"index":1},{"value":12,"source":1,"index":2},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":12,"source":1,"index":2}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[1,2,1]- heap
[{"value":12,"source":1,"index":2},{"value":18,"source":2,"index":1}]- held
{"value":10,"source":0,"index":1}- frontier
[{"value":10,"source":0,"index":1},{"value":12,"source":1,"index":2},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[10,18]- width
8- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[2,2,1]- heap
[{"value":12,"source":1,"index":2},{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1}]- held
null- frontier
[{"value":12,"source":1,"index":2},{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":15,"source":0,"index":2}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[2,2,1]- heap
[{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1}]- held
{"value":12,"source":1,"index":2}- frontier
[{"value":12,"source":1,"index":2},{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1}]- maximum
18- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[12,18]- width
6- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[2,3,1]- heap
[{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3}]- held
null- frontier
[{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3}]- maximum
20- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":20,"source":1,"index":3}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[2,3,1]- heap
[{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3}]- held
{"value":15,"source":0,"index":2}- frontier
[{"value":15,"source":0,"index":2},{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3}]- maximum
20- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[15,20]- width
5- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[3,3,1]- heap
[{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3},{"value":24,"source":0,"index":3}]- held
null- frontier
[{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3},{"value":24,"source":0,"index":3}]- maximum
24- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":24,"source":0,"index":3}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[3,3,1]- heap
[{"value":20,"source":1,"index":3},{"value":24,"source":0,"index":3}]- held
{"value":18,"source":2,"index":1}- frontier
[{"value":18,"source":2,"index":1},{"value":20,"source":1,"index":3},{"value":24,"source":0,"index":3}]- maximum
24- best
[0,5]- bestWidth
5- phase
"candidate"- candidate
[18,24]- width
6- oldBest
[0,5]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[3,3,2]- heap
[{"value":20,"source":1,"index":3},{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- held
null- frontier
[{"value":20,"source":1,"index":3},{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- maximum
24- best
[0,5]- bestWidth
5- phase
"advance"- successor
{"value":22,"source":2,"index":2}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[3,3,2]- heap
[{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- held
{"value":20,"source":1,"index":3}- frontier
[{"value":20,"source":1,"index":3},{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- maximum
24- best
[20,24]- bestWidth
4- phase
"candidate"- candidate
[20,24]- width
4- oldBest
[0,5]
- Stop after evaluating the last valid candidate for this source.
The limiting source has no successor; advancing other sources cannot improve this already evaluated left boundary.
- lists
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]- positions
[3,3,2]- heap
[{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- held
{"value":20,"source":1,"index":3}- frontier
[{"value":20,"source":1,"index":3},{"value":22,"source":2,"index":2},{"value":24,"source":0,"index":3}]- maximum
24- best
[20,24]- bestWidth
4- phase
"exhausted"- exhaustedSource
1
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[20,24]
Equal widths prefer smaller starts
Input: [[1,4],[2,5]] · Inclusive covering range: [1,2]
Step 1 of 8: Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
Phase: initial. Current maximum: 2. Best inclusive range: [1, 2], long width 1.
Complete candidate frontier — one occurrence per source
- source 0, index 0: 1 (queued)
- source 1, index 0: 2 (queued)
Actual heap after any poll — minimum priority first
- source 0: 1
- source 1: 2
The held record remains part of coverage after poll; the heap alone may contain only k−1 sources. Stop only after evaluating the exhausted source’s last valid candidate.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lists | [[1,4],[2,5]] |
| positions | [0,0] |
| heap | [{"value":1,"source":0,"index":0},{"value":2,"source":1,"index":0}] |
| held | null |
| frontier | [{"value":1,"source":0,"index":0},{"value":2,"source":1,"index":0}] |
| maximum | 2 |
| best | [1,2] |
| bestWidth | 1 |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.PriorityQueue; 5 public final class Solution { 6 private record Entry(int value, int source, int index) {} 7 private static final Comparator<Entry> ORDER = Comparator.comparingInt(Entry::value).thenComparingInt(Entry::source).thenComparingInt(Entry::index); 8 private static void validate(int[][] lists) { 9 Objects.requireNonNull(lists, "lists"); 10 if (lists.length == 0) throw new IllegalArgumentException("no lists"); 11 for (int[] row : lists) if (row == null || row.length == 0) throw new IllegalArgumentException("empty list"); 12 } 13 private static boolean better(int lo, int hi, int bestLo, int bestHi) { 14 long width = (long) hi - lo, bestWidth = (long) bestHi - bestLo; 15 return width < bestWidth || width == bestWidth && lo < bestLo; 16 } 17 public static int[] smallestRange(int[][] lists) { 18 validate(lists); 19 PriorityQueue<Entry> current = new PriorityQueue<>(ORDER); 20 int maximum = Integer.MIN_VALUE; 21 for (int i = 0; i < lists.length; i++) { 22 current.offer(new Entry(lists[i][0],i,0)); 23 maximum = Math.max(maximum,lists[i][0]); 24 } 25 int bestLo = current.peek().value, bestHi = maximum; 26 while (true) { 27 Entry minimum = current.poll(); 28 if (better(minimum.value,maximum,bestLo,bestHi)) { bestLo = minimum.value; bestHi = maximum; } 29 int next = minimum.index + 1; 30 if (next == lists[minimum.source].length) break; 31 int value = lists[minimum.source][next]; 32 current.offer(new Entry(value,minimum.source,next)); 33 maximum = Math.max(maximum,value); 34 } 35 return new int[]{bestLo,bestHi}; 36 } 37 public static int[] baseline(int[][] lists) { 38 validate(lists); 39 ArrayList<Entry> all = new ArrayList<>(); 40 for (int s = 0; s < lists.length; s++) for (int i = 0; i < lists[s].length; i++) all.add(new Entry(lists[s][i],s,i)); 41 all.sort(ORDER); 42 int[] counts = new int[lists.length]; 43 int covered = 0, left = 0, bestLo = all.get(0).value, bestHi = all.get(all.size()-1).value; 44 for (int right = 0; right < all.size(); right++) { 45 if (counts[all.get(right).source]++ == 0) covered++; 46 while (covered == lists.length) { 47 int lo = all.get(left).value, hi = all.get(right).value; 48 if (better(lo,hi,bestLo,bestHi)) { bestLo = lo; bestHi = hi; } 49 if (--counts[all.get(left++).source] == 0) covered--; 50 } 51 } 52 return new int[]{bestLo,bestHi}; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
- lists
[[1,4],[2,5]]- positions
[0,0]- heap
[{"value":1,"source":0,"index":0},{"value":2,"source":1,"index":0}]- held
null- frontier
[{"value":1,"source":0,"index":0},{"value":2,"source":1,"index":0}]- maximum
2- best
[1,2]- bestWidth
1- phase
"initial"
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[1,4],[2,5]]- positions
[0,0]- heap
[{"value":2,"source":1,"index":0}]- held
{"value":1,"source":0,"index":0}- frontier
[{"value":1,"source":0,"index":0},{"value":2,"source":1,"index":0}]- maximum
2- best
[1,2]- bestWidth
1- phase
"candidate"- candidate
[1,2]- width
1- oldBest
[1,2]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[1,4],[2,5]]- positions
[1,0]- heap
[{"value":2,"source":1,"index":0},{"value":4,"source":0,"index":1}]- held
null- frontier
[{"value":2,"source":1,"index":0},{"value":4,"source":0,"index":1}]- maximum
4- best
[1,2]- bestWidth
1- phase
"advance"- successor
{"value":4,"source":0,"index":1}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[1,4],[2,5]]- positions
[1,0]- heap
[{"value":4,"source":0,"index":1}]- held
{"value":2,"source":1,"index":0}- frontier
[{"value":2,"source":1,"index":0},{"value":4,"source":0,"index":1}]- maximum
4- best
[1,2]- bestWidth
1- phase
"candidate"- candidate
[2,4]- width
2- oldBest
[1,2]
- Replace only the limiting witness and update the maximum.
A complete one-per-source frontier is restored; its maximum cannot decrease under sorted input.
- lists
[[1,4],[2,5]]- positions
[1,1]- heap
[{"value":4,"source":0,"index":1},{"value":5,"source":1,"index":1}]- held
null- frontier
[{"value":4,"source":0,"index":1},{"value":5,"source":1,"index":1}]- maximum
5- best
[1,2]- bestWidth
1- phase
"advance"- successor
{"value":5,"source":1,"index":1}
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[1,4],[2,5]]- positions
[1,1]- heap
[{"value":5,"source":1,"index":1}]- held
{"value":4,"source":0,"index":1}- frontier
[{"value":4,"source":0,"index":1},{"value":5,"source":1,"index":1}]- maximum
5- best
[1,2]- bestWidth
1- phase
"candidate"- candidate
[4,5]- width
1- oldBest
[1,2]
- Stop after evaluating the last valid candidate for this source.
The limiting source has no successor; advancing other sources cannot improve this already evaluated left boundary.
- lists
[[1,4],[2,5]]- positions
[1,1]- heap
[{"value":5,"source":1,"index":1}]- held
{"value":4,"source":0,"index":1}- frontier
[{"value":4,"source":0,"index":1},{"value":5,"source":1,"index":1}]- maximum
5- best
[1,2]- bestWidth
1- phase
"exhausted"- exhaustedSource
0
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[1,2]
Integer extremes require a long width
Input: [[-2147483648],[2147483647]] · Inclusive covering range: [-2147483648,2147483647]
Step 1 of 4: Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
Phase: initial. Current maximum: 2147483647. Best inclusive range: [-2147483648, 2147483647], long width 4294967295.
Complete candidate frontier — one occurrence per source
- source 0, index 0: -2147483648 (queued)
- source 1, index 0: 2147483647 (queued)
Actual heap after any poll — minimum priority first
- source 0: -2147483648
- source 1: 2147483647
The held record remains part of coverage after poll; the heap alone may contain only k−1 sources. Stop only after evaluating the exhausted source’s last valid candidate.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lists | [[-2147483648],[2147483647]] |
| positions | [0,0] |
| heap | [{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}] |
| held | null |
| frontier | [{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}] |
| maximum | 2147483647 |
| best | [-2147483648,2147483647] |
| bestWidth | 4294967295 |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.PriorityQueue; 5 public final class Solution { 6 private record Entry(int value, int source, int index) {} 7 private static final Comparator<Entry> ORDER = Comparator.comparingInt(Entry::value).thenComparingInt(Entry::source).thenComparingInt(Entry::index); 8 private static void validate(int[][] lists) { 9 Objects.requireNonNull(lists, "lists"); 10 if (lists.length == 0) throw new IllegalArgumentException("no lists"); 11 for (int[] row : lists) if (row == null || row.length == 0) throw new IllegalArgumentException("empty list"); 12 } 13 private static boolean better(int lo, int hi, int bestLo, int bestHi) { 14 long width = (long) hi - lo, bestWidth = (long) bestHi - bestLo; 15 return width < bestWidth || width == bestWidth && lo < bestLo; 16 } 17 public static int[] smallestRange(int[][] lists) { 18 validate(lists); 19 PriorityQueue<Entry> current = new PriorityQueue<>(ORDER); 20 int maximum = Integer.MIN_VALUE; 21 for (int i = 0; i < lists.length; i++) { 22 current.offer(new Entry(lists[i][0],i,0)); 23 maximum = Math.max(maximum,lists[i][0]); 24 } 25 int bestLo = current.peek().value, bestHi = maximum; 26 while (true) { 27 Entry minimum = current.poll(); 28 if (better(minimum.value,maximum,bestLo,bestHi)) { bestLo = minimum.value; bestHi = maximum; } 29 int next = minimum.index + 1; 30 if (next == lists[minimum.source].length) break; 31 int value = lists[minimum.source][next]; 32 current.offer(new Entry(value,minimum.source,next)); 33 maximum = Math.max(maximum,value); 34 } 35 return new int[]{bestLo,bestHi}; 36 } 37 public static int[] baseline(int[][] lists) { 38 validate(lists); 39 ArrayList<Entry> all = new ArrayList<>(); 40 for (int s = 0; s < lists.length; s++) for (int i = 0; i < lists[s].length; i++) all.add(new Entry(lists[s][i],s,i)); 41 all.sort(ORDER); 42 int[] counts = new int[lists.length]; 43 int covered = 0, left = 0, bestLo = all.get(0).value, bestHi = all.get(all.size()-1).value; 44 for (int right = 0; right < all.size(); right++) { 45 if (counts[all.get(right).source]++ == 0) covered++; 46 while (covered == lists.length) { 47 int lo = all.get(left).value, hi = all.get(right).value; 48 if (better(lo,hi,bestLo,bestHi)) { bestLo = lo; bestHi = hi; } 49 if (--counts[all.get(left++).source] == 0) covered--; 50 } 51 } 52 return new int[]{bestLo,bestHi}; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one coverage witness from each source.
The complete frontier covers all lists; maximum is its largest current value.
- lists
[[-2147483648],[2147483647]]- positions
[0,0]- heap
[{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}]- held
null- frontier
[{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}]- maximum
2147483647- best
[-2147483648,2147483647]- bestWidth
4294967295- phase
"initial"
- Evaluate the held minimum together with the remaining heap.
After poll the heap alone has k−1 entries; the held minimum is still part of this valid covering candidate. Width is computed in long in Java.
- lists
[[-2147483648],[2147483647]]- positions
[0,0]- heap
[{"value":2147483647,"source":1,"index":0}]- held
{"value":-2147483648,"source":0,"index":0}- frontier
[{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}]- maximum
2147483647- best
[-2147483648,2147483647]- bestWidth
4294967295- phase
"candidate"- candidate
[-2147483648,2147483647]- width
4294967295- oldBest
[-2147483648,2147483647]
- Stop after evaluating the last valid candidate for this source.
The limiting source has no successor; advancing other sources cannot improve this already evaluated left boundary.
- lists
[[-2147483648],[2147483647]]- positions
[0,0]- heap
[{"value":2147483647,"source":1,"index":0}]- held
{"value":-2147483648,"source":0,"index":0}- frontier
[{"value":-2147483648,"source":0,"index":0},{"value":2147483647,"source":1,"index":0}]- maximum
2147483647- best
[-2147483648,2147483647]- bestWidth
4294967295- phase
"exhausted"- exhaustedSource
0
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[-2147483648,2147483647]
Test the contract
Input:
One nonempty sorted row
Output:[first,first]Width-zero tie uses smallest start.
Input:
[[1,4],[2,5]]
Output:[1,2]Deterministic equal-width tie.
Input:
Classic three lists
Output:[20,24]Unequal lengths and moving maximum.
Input:
[[MIN],[MAX]]
Output:[MIN,MAX]Long width.
Input:
No lists or an empty row
Output:IllegalArgumentExceptionCoverage is infeasible under this API.
Common mistakes and counterexamples
Continue after a source is exhausted
Counterexample: A later two-source interval cannot solve a three-source coverage request.
Evaluate the last valid candidate and then stop.
Forget a source label on equal values
Counterexample: Two equal numbers from the same source do not cover two different sources.
Track source and occurrence index for each frontier entry.
Subtract endpoints as int
Counterexample: MAX−MIN wraps negative and can falsely look optimal.
Use (long)hi−lo before comparing widths.
Show only the heap after polling as covered
Counterexample: The heap temporarily has k−1 entries.
Include the held minimum in the candidate set and distinguish it from queued entries.
Follow-ups
Return the covering occurrences too.
Retain or reconstruct one source-labelled witness per list for the winning range. Copying a whole frontier on every improvement adds O(k) per update; use a second pass or account for that work.
Inputs are sorted streams.
The same one-head frontier works while each stream can supply its next value. Define exhaustion/failure behavior, buffering, and whether the result is knowable before all potentially improving prefixes arrive.
Use another tie rule.
Equal width plus smaller start is the current total objective; largest start or lexicographic witness identities changes update conditions and tests. The coverage proof survives, but deterministic selection must match the declared ranking.