Find the Smallest Range Covering K Sorted Lists

Problem Statement

You are given k lists of sorted integers in non-decreasing order. Your task is to find the smallest inclusive range [a, b] that contains at least one number from each of the k lists.

A range [a, b] is defined as smaller than [c, d] if:

1. b - a < d - c (the interval length is strictly smaller), or
2. b - a == d - c and a < c (tie-breaker: choose the range with the smaller lower bound).

Lists may contain duplicate values as well as negative integers.

Function Signature

def smallest_range(nums: list[list[int]]) -> list[int]:
    pass

Input & Output Format

• Input: nums, a 2D list of integers where each sublist nums[i] is sorted in non-decreasing order.
• Output: A list of two integers [a, b] representing the smallest valid range.

Constraints

• k == len(nums)
• 1 <= k <= 3500
• 1 <= len(nums[i]) <= 50
• Total number of elements across all lists does not exceed 10^5
• -10^5 <= nums[i][j] <= 10^5
• Each nums[i] is sorted in non-decreasing order

Examples

Example 1

Input: nums = [
  [4, 10, 15, 24, 26],
  [0, 9, 12, 20],
  [5, 18, 22, 30]
]
Output: [20, 24]
Explanation:
- List 0 provides: 24
- List 1 provides: 20
- List 2 provides: 22
Range [20, 24] has length 4 and covers all 3 lists. No smaller range covers all lists.

Example 2

Input: nums = [
  [1, 2, 3],
  [1, 2, 3],
  [1, 2, 3]
]
Output: [1, 1]
Explanation:
Range [1, 1] contains 1 from each list, with length 0. Both [2, 2] and [3, 3] also have length 0, but [1, 1] is chosen because of the smaller left endpoint tie-breaker.

Edge Cases to Consider

• k = 1: The answer should be [nums[0][0], nums[0][0]].
• Overlapping identical values across lists.
• Negative numbers and ranges that cross zero (e.g., [-10, -5] or [-2, 3]).