Heap / Priority Queue
LC #632Hard
Smallest Range Covering Elements from K Lists
Heap / Priority Queue
GoogleAmazonBloombergProblem
Find the smallest range [a, b] such that at least one element from each of the k sorted lists lies in the range.
heapsliding-windowsorting
Constraints
- ›nums.length == k
- ›1 ≤ k ≤ 3500
- ›1 ≤ nums[i].length ≤ 50
- ›-10⁵ ≤ nums[i][j] ≤ 10⁵
- ›Each nums[i] is sorted ascending
Example
Input
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]Output
[20,24]Why
[20,24] contains 24 (list 0), 20 (list 1), 22 (list 2)