Smallest Range Covering Elements from K Lists

You are given k lists of integers in nums; each list is sorted in non-decreasing order.

Find the shortest closed interval [a, b] of integers such that every list has at least one element x with a <= x <= b.

Intervals are compared by length b - a: shorter is better. When two intervals have the same length, the one with the smaller start a is better. Return the best interval as [a, b]. (An optimal interval can always be chosen with both endpoints taken from the lists, so the answer is unique under this rule.)

Example 1

Example 2

Example 3

Constraints

• 1 <= k = nums.length <= 3500
• 1 <= nums[i].length <= 50
• -105 <= nums[i][j] <= 105
• Each nums[i] is sorted in non-decreasing order.

Pattern Path · Heaps & Top-K · problem 107 of 169

Start simple

Merge all N values, then for every candidate start try every end and check coverage of all k lists: O(N²·k), or O(N²) with a counting window per start.

The key idea

Picture one pointer in each list. The pointed-at values form a set that touches every list, and the tightest interval covering that set is [min, max]. Every optimal interval corresponds to some choice of pointers, so we only need to visit the right pointer positions.

Begin with all pointers at the front. Why is it safe to move only the pointer at the minimum? Let m be the current minimum. In every other list the pointer sits on the first element that is at least m, because each element before it was popped earlier as a minimum and so was no larger than m. Hence the current maximum is the smallest possible right end for an interval starting at m, and [m, max] is the best interval with that start. Once it is recorded, m is no longer needed: advance its list's pointer, update the maximum, and repeat.

A min-heap holding one (value, list, index) entry per list gives the minimum in O(log k); the maximum only ever grows, so a single variable tracks it. Record [min, max] each round, replacing the best only on a strictly shorter span. Since minimums come out in non-decreasing order, ties automatically keep the smaller start. When the minimum's list has no next element, no future interval can cover that list with a larger left end, so the search is over.

Complexity

• Time: O(N log k), where N is the total number of elements
• Space: O(k)

Python

class Solution:
    def smallestRange(self, nums):
        # The heap holds exactly one "current" element from every list:
        # (value, which list, position in that list).
        heap = [(values[0], i, 0) for i, values in enumerate(nums)]
        heapify(heap)
        high = max(values[0] for values in nums)
        best = [heap[0][0], high]

        while True:
            low, i, j = heappop(heap)
            # [low, high] covers one element of every list.
            # Strict "<" keeps the earlier (smaller-start) range on ties.
            if high - low < best[1] - best[0]:
                best = [low, high]
            if j + 1 == len(nums[i]):
                return best  # list i is used up: the minimum can never rise again
            nxt = nums[i][j + 1]
            high = max(high, nxt)
            heappush(heap, (nxt, i, j + 1))

JavaScript

class MinHeap {
  constructor(less) {
    this.items = [];
    this.less = less;
  }
  push(item) {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!this.less(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }
  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var smallestRange = function(nums) {
  // The heap holds exactly one "current" element from every list:
  // [value, which list, position in that list].
  const heap = new MinHeap((x, y) => x[0] < y[0]);
  let high = -Infinity;
  nums.forEach((values, i) => {
    heap.push([values[0], i, 0]);
    high = Math.max(high, values[0]);
  });
  let best = [heap.items[0][0], high];

  while (true) {
    const [low, i, j] = heap.pop();
    // [low, high] covers one element of every list.
    // Strict "<" keeps the earlier (smaller-start) range on ties.
    if (high - low < best[1] - best[0]) best = [low, high];
    if (j + 1 === nums[i].length) return best; // list i is used up
    const nxt = nums[i][j + 1];
    high = Math.max(high, nxt);
    heap.push([nxt, i, j + 1]);
  }
};

What the interviewer is checking

This tests whether you can generalise merging k sorted lists with a heap into a moving window, and justify why only the minimum pointer should ever move.

Mistakes to avoid

• Advancing the pointer of the maximum instead of the minimum, which can only widen the interval.
• Updating the best range on equal length, which breaks the smaller-start tie rule.
• Continuing after one list is exhausted; the interval must still contain an element of that list.
• Recomputing the maximum over the whole heap each step (O(k)) instead of tracking it as values are pushed.

Follow-ups to expect

• Can you solve it without a heap? (Merge with list tags, sliding window.)
• What if the lists are huge streams? (Same heap, one value per stream.)
• What if the interval only needs to touch m of the k lists? (Sliding window counting distinct lists.)

In real software

Search engines rank documents by the tightest span containing every query term, using the term position lists exactly like the k sorted lists here.

Practice next