Smallest Range Covering Elements from K Lists

HardHeapheap + sliding window

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given k lists of integers, where every individual list is sorted in non-decreasing order. Your task is to find the smallest possible range [a, b] such that **at least one number from each of the k lists** falls within that range (inclusive). A range [a, b] is considered **smaller** than another range [c, d] if b - a < d - c. If the two ranges have the same width, the one with the smaller starting value a is preferred. You should return the range as a two-element array [a, b]. The classic approach treats this as a sliding window over the merged ordering of all elements: maintain one active candidate from every list. The window is valid as long as it contains a representative from each list, and you shrink it by advancing the smallest current element. A min-heap that always surfaces the current minimum (while you separately track the current maximum) lets you do this efficiently without merging everything explicitly. The input is provided as a 2D array nums, where nums[i] is the i-th sorted list.

Examples

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
The range [20,24] contains 24 from list 0, 20 from list 1, and 22 from list 2. No tighter range (width 4) covers all three lists.
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
Picking 1 from each list yields the degenerate range [1,1] with width 0, which is optimal.
Input: nums = [[10],[11]]
Output: [10,11]
Each list has a single element, so the only possible range spans both: [10,11].

Constraints

  • `nums.length == k`
  • `1 <= k <= 3500`
  • `1 <= nums[i].length <= 50`
  • `-10^5 <= nums[i][j] <= 10^5`
  • Each `nums[i]` is sorted in non-decreasing order.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.