Smallest Range Covering Elements from K Lists
Hard · Heap & Counting · Array · Hash Table · Greedy · Sliding Window · Sorting · Heap (Priority Queue)
Problem
You are given k lists of integers nums, each sorted in non-decreasing order. Find the smallest range [a, b] that contains at least one number from every list.
A range [a, b] is smaller than [c, d] if b - a < d - c, or if b - a == d - c and a < c. Return the smallest range as [a, b].
Examples
Input: nums = [[1,9,20],[4,12],[8,10,30]] Output: [9,12]
[9, 12] holds 9 from the first list, 12 from the second and 10 from the third; no narrower range covers all three.
Input: nums = [[5,7],[5,8],[5]] Output: [5,5]
5 is in every list, so a range of width 0 works.
Input: nums = [[-3,0],[2,6]] Output: [0,2]
Pairing 0 with 2 gives width 2, the smallest possible.
Constraints
- k == len(nums)
- 1 <= k <= 3500
- 1 <= len(nums[i]) <= 50
- -10^5 <= nums[i][j] <= 10^5
- each nums[i] is sorted in non-decreasing order
Approaches
- Baseline: try every left end — time O(N · k log L), space O(N)
Follow-up
The heap walk is a k-way merge with a window on top: it visits the numbers in sorted order and keeps exactly one from each list. Merging everything into one sorted list of (value, list) pairs and sliding a window that covers all k labels gives the same answer; that is the first use case below. With exactly three lists, three pointers replace the heap.
Related problems
Start free on Cariara · Coding problems · System design studio
