Show problems as
Classic problem #632HardArrayHash TableGreedySliding WindowSortingHeap (Priority Queue)

Smallest Range Covering Elements from K Lists

Real-world version: Tightest Gauge Band
Tracked in this browser only
Read Smallest Range Covering Elements from K Lists on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMerge K Lists · Priority Queues, animated step by step

A field survey runs k gauges. Gauge i filed the readings in nums[i], already arranged from lowest to highest, and every gauge filed at least one reading.

Calibration needs a single band of values that reaches every gauge. A band is written [low, high] with low <= high, and it reaches a gauge when at least one of that gauge's readings sits inside the band, endpoints included.

Return the tightest band that reaches all k gauges. Tightest means the smallest high - low. When several bands tie on that width, return the one whose low is smallest.

Examples

Example 1

Input
nums = [[2,11,17],[6,13],[-4,9,15]]
Output
[9, 13]

The band [9,13] holds 11 from the first gauge, 13 from the second and 9 from the third, so it reaches all three and its width is 4.

Example 2

Input
nums = [[1,5],[3,7]]
Output
[1, 3]

Three bands reach both gauges at width 2: [1,3], [3,5] and [5,7]. The tie goes to the smallest low, so the answer is [1,3].

Example 3

Input
nums = [[8]]
Output
[8, 8]

With one gauge and one reading, the band [8,8] already reaches it and has width 0.

Example 4

Input
nums = [[-100000,100000],[0]]
Output
[-100000, 0]

The second gauge only ever reads 0, so a band must stretch from 0 to one of -100000 or 100000. Both give width 100000, and the smaller low wins.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_range(nums: list[list[int]]) -> list[int]:
Java
public int[] smallestRange(List<List<Integer>> nums)

More on the same topics