0360HardArrayHash TableGreedySliding WindowSortingHeap (Priority Queue)

Tightest Gauge Band

Tracked in this browser only

Trains the technique from

LeetCode 632Smallest Range Covering Elements from K Lists

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public int[] smallestRange(List<List<Integer>> nums)

The intended approach

Time O(N log k) where N is the total number of readingsSpace O(k) for the heap

Hold one cursor per gauge and keep the k cursor readings in a min-heap while tracking the largest of them in a separate variable. The heap top and that variable are the low and high of a band that reaches every gauge, so record its width, then pop the smallest reading and push the next one from the same gauge. Because pops come out in non-decreasing order, updating the best only on a strictly smaller width automatically keeps the smallest low among ties, and the walk ends the moment a gauge runs out of readings.

Pythonentry point: smallest_range

import heapq


def smallest_range(nums):
    # N = total readings, k = number of gauges.
    # Time O(N log k), space O(k) for the heap; the answer itself is two values.
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    high = max(lst[0] for lst in nums)
    best_low, best_high = -10 ** 9, 10 ** 9
    while True:
        low, i, j = heapq.heappop(heap)
        if high - low < best_high - best_low:
            best_low, best_high = low, high
        if j + 1 == len(nums[i]):
            return [best_low, best_high]
        nxt = nums[i][j + 1]
        if nxt > high:
            high = nxt
        heapq.heappush(heap, (nxt, i, j + 1))

The obvious version

Collect every distinct reading, try all ordered pairs of them as low and high, keep the pairs that reach every gauge and pick the best by width then by low.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_range(nums):
    values = sorted({v for lst in nums for v in lst})
    best = None
    for a in range(len(values)):
        for b in range(a, len(values)):
            low, high = values[a], values[b]
            ok = True
            for lst in nums:
                if not any(low <= v <= high for v in lst):
                    ok = False
                    break
            if not ok:
                continue
            if best is None:
                best = [low, high]
            elif high - low < best[1] - best[0]:
                best = [low, high]
            elif high - low == best[1] - best[0] and low < best[0]:
                best = [low, high]
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in