Skip to main content

632. Smallest Range Covering Elements from K Lists

hard

Find the shortest range that contains at least one number from each of k sorted lists. A k-way-merge variant where the heap holds one pointer per list and the answer is the range across them.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

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.

Examples

Example 1

Input
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output
[20,24]

Explanation: List 1: [24, 26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2

Input
nums = [[1,2,3],[1,2,3],[1,2,3]]
Output
[1,1]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

At any moment, the range covering one element from each list is [min(currentPointers), max(currentPointers)].

Hint 2

To shrink the range, advance the pointer at the minimum value — it's the bottleneck.

Hint 3

Min-heap of (value, listIndex, indexInList). Track the current max separately. Pop the min, update the range if better, advance that list's pointer, push the new value, and update the max.

Hint 4

Stop the moment a list runs out — you can no longer cover all k lists.

Solution approach

Reveal approach

Min-heap of (value, listIdx, posIdx). Seed with the first element of every list and track the maximum among those firsts as 'curMax'. Loop: pop the min — the current range is [minVal, curMax]. If curMax - minVal beats the best so far, update the answer. To shrink, advance the popped list's pointer; if it has no next element return the current best. Otherwise push the new value (val, listIdx, posIdx+1) and update curMax. The min-heap gives you the smallest-of-pointers in O(log k); curMax is just maintained as you push. Total O(N log k) where N is total elements. The 'stop when any list exhausts' termination is key — you can't validly cover all k once one runs dry.

Complexity

Time
O(N log k)
Space
O(k)

Related patterns

  • heap
  • k-way-merge
  • sliding-window

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Smallest Range Covering Elements from K Lists and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →