434. Smallest Range Covering Elements from K Lists
You are given k lists of integers, each one already sorted in non-decreasing order. Find the smallest closed range [a, b] that contains at least one number from every list.
Range [a, b] beats range [c, d] when it is narrower (b − a < d − c), or when the widths tie and it starts lower (a < c). This ordering makes the answer unique.
Your function receives nums, a list of k sorted integer lists, and returns the winning range as a pair [a, b].
Example 1:
Input: nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
Output: [20, 24]
Explanation: The range [20, 24] has width 4 and touches all three lists: 24 from the first, 20 from the second, 22 from the third. No range of width 3 or less covers all of them.
Example 2:
Input: nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Output: [1, 1]
Explanation: Width-0 ranges [1, 1], [2, 2], and [3, 3] all cover every list; the tie-break picks the one with the smallest start.
Constraints:
- 1 ≤ k ≤ 500
- 1 ≤ nums[i].length ≤ 50
- -10⁵ ≤ nums[i][j] ≤ 10⁵
- Each nums[i] is sorted in non-decreasing order.
Hints:
Any candidate range is pinned by its endpoints, and the best range's low endpoint is always some element of some list. Imagine merging all lists into one sorted stream where every value remembers which list it came from — the problem becomes: find the shortest window of the stream that contains all k list labels at least once.
Instead of materializing the merge, keep one cursor per list and a min-heap of the k cursor values, plus the current maximum among them. The heap top and the max span a range covering all lists; pop the min and advance its cursor to try to shrink from below. When some list runs out, no further range exists. Update the best only on a STRICT improvement so the width/start tie-break holds.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
Expected output: [20, 24]