algorythms
Heap / Priority Queue
LC #632Hard

Smallest Range Covering Elements from K Lists

Heap / Priority Queue
GoogleAmazonBloomberg

Problem

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

Inputnums = [[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)

Hints — reveal one at a time