Find the Smallest Range Covering K Sorted Lists
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Find the Smallest Range Covering K Sorted Lists
Implement `smallest_covering_range(nums)`. `nums` contains `k` nonempty integer lists, each sorted in nondecreasing order. Return a two-element list `[left, right]` describing an inclusive range that contains at least one number from every input list.
Choose the range with the smallest width `right - left`. If multiple ranges have the same width, choose the one with the smaller `left` endpoint.
## Function Contract
`smallest_covering_range(nums: list[list[int]]) -> list[int]`
## Constraints
- `1 <= len(nums) <= 3500`
- `1 <= len(nums[i])`
- The total number of integers across all lists is at most `200000`.
- `-10^9 <= nums[i][j] <= 10^9`
- Each inner list is sorted in nondecreasing order and may contain duplicates.
## Examples
### Example 1
```text
Input: [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
Output: [20, 24]
```
The range contains `24` from the first list, `20` from the second, and `22` from the third.
### Example 2
```text
Input: [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Output: [1, 1]
```
The value `1` appears in every list, so a zero-width range is optimal and the tie rule selects the smallest endpoint.
Overview: Find the narrowest inclusive range containing at least one value from each of several sorted integer lists. The prompt defines duplicate handling, negative values, total input size, and a deterministic smaller-left-endpoint tie break for later four-language console verification.
Read the full Snapchat Machine Learning Engineer interview experience this question came from
Given k nonempty integer lists sorted in nondecreasing order, return an inclusive range [left, right] containing at least one number from every list. Minimize right-left; if widths tie, choose the smaller left endpoint. Duplicates are allowed.
Constraints
- 1 <= nums.length <= 3,500
- Every inner list is nonempty and sorted in nondecreasing order.
- The total number of integers is at most 200,000.
- -10^9 <= nums[i][j] <= 10^9
- Equal widths are resolved by the smaller left endpoint.
Examples
Input: ([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]],)
Expected Output: [20, 24]
Explanation: The interval covers 24, 20, and 22 and has minimum width.
Input: ([[1, 2, 3], [1, 2, 3], [1, 2, 3]],)
Expected Output: [1, 1]
Explanation: A common value gives width zero; the smallest common endpoint wins.
Hints
- A candidate range needs one current value from each list.
- Advance the list holding the current minimum and maintain the current maximum.