632. Smallest Range Covering Elements from K Lists

Quick Identifier

Topic: heap-priority-queue
Pattern: Top-K / Heap (k-way min tracking + global max) with Sliding Window-style pointer advance
Difficulty: Hard
Companies: Google, Amazon, Microsoft, LinkedIn, DoorDash
Frequency: High
LeetCode: 632

Quick Sights

Time Complexity: k from the optimal approach.
Space Complexity: maxValue from the optimal approach.
Core Mechanism: You are given k sorted integer lists. Choose exactly one number from each list (any position) so that the numeric range from min to max among those k picks is as small as possible. Return [min, max] for an optimal choice (any smallest range if tied).

You are given k sorted integer lists. Choose exactly one number from each list (any position) so that the numeric range from min to max among those k picks is as small as possible. Return [min, max] for an optimal choice (any smallest range if tied).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

“Smallest range” across k sorted streams with one pick per stream
Always maintain one active element per list — the best configuration is discoverable by advancing only the list that currently contributes the minimum (greedy + exchange argument)
Naive: all combinations — need heap + running maximum

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — enumerate all tuples of indices — product of list sizes, intractable.
Better — for each possible min value, binary search in other lists — still messy and log factors stack.
Acceptable — merge all values with (value, listId) tags, then slide a window that hits all lists — O(n log n) if you sort n total elements; worse than needed.
Optimal — min-heap of size k over the current head of each list, track maxValue over those heads, repeatedly pop min and push next from the same list — O(n log k) time / O(k) space for n = total elements across lists.

Optimal Solution

Go

import "container/heap"

type listHead struct {
	value     int
	listIndex int
	nextIndex int
}

type minByValue []listHead

func (items minByValue) Len() int { return len(items) }
func (items minByValue) Less(indexA, indexB int) bool {
	return items[indexA].value < items[indexB].value
}
func (items minByValue) Swap(indexA, indexB int) { items[indexA], items[indexB] = items[indexB], items[indexA] }

func (items *minByValue) Push(value any) {
	*items = append(*items, value.(listHead))
}

func (items *minByValue) Pop() any {
	old := *items
	lastIndex := len(old) - 1
	popped := old[lastIndex]
	*items = old[:lastIndex]
	return popped
}

func smallestRange(lists [][]int) []int {
	active := &minByValue{}
	heap.Init(active)
	maxValue := 0
	for listIndex, numbers := range lists {
		firstValue := numbers[0]
		heap.Push(active, listHead{
			value:     firstValue,
			listIndex: listIndex,
			nextIndex: 1,
		})
		if listIndex == 0 || firstValue > maxValue {
			maxValue = firstValue
		}
	}
	// invariant: heap root is the current minimum among the k chosen front elements
	bestLow := (*active)[0].value
	bestHigh := maxValue
	for {
		smallest := heap.Pop(active).(listHead)
		if smallest.nextIndex >= len(lists[smallest.listIndex]) {
			break
		}
		nextValue := lists[smallest.listIndex][smallest.nextIndex]
		if nextValue > maxValue {
			maxValue = nextValue
		}
		heap.Push(active, listHead{
			value:     nextValue,
			listIndex: smallest.listIndex,
			nextIndex: smallest.nextIndex + 1,
		})
		newMin := (*active)[0].value
		if maxValue-newMin < bestHigh-bestLow {
			bestLow = newMin
			bestHigh = maxValue
		}
	}
	return []int{bestLow, bestHigh}
}

JavaScript

class MinHeap {
  constructor() {
    this.values = [];
  }
  push(entry) {
    this.values.push(entry);
    this.bubbleUp(this.values.length - 1);
  }
  pop() {
    const top = this.values[0];
    const last = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }
  peek() {
    return this.values[0];
  }
  get size() {
    return this.values.length;
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.values[parentIndex].value <= this.values[index].value) {
        break;
      }
      [this.values[parentIndex], this.values[index]] = [
        this.values[index],
        this.values[parentIndex],
      ];
      index = parentIndex;
    }
  }
  bubbleDown(index) {
    const length = this.values.length;
    while (true) {
      const leftIndex = index * 2 + 1;
      const rightIndex = index * 2 + 2;
      let smallest = index;
      if (
        leftIndex < length &&
        this.values[leftIndex].value < this.values[smallest].value
      ) {
        smallest = leftIndex;
      }
      if (
        rightIndex < length &&
        this.values[rightIndex].value < this.values[smallest].value
      ) {
        smallest = rightIndex;
      }
      if (smallest === index) {
        break;
      }
      [this.values[index], this.values[smallest]] = [
        this.values[smallest],
        this.values[index],
      ];
      index = smallest;
    }
  }
}

function smallestRange(lists) {
  const heap = new MinHeap();
  let maxValue = Number.NEGATIVE_INFINITY;
  for (let listIndex = 0; listIndex < lists.length; listIndex++) {
    const firstValue = lists[listIndex][0];
    heap.push({
      value: firstValue,
      listIndex,
      nextIndex: 1,
    });
    maxValue = Math.max(maxValue, firstValue);
  }
  let bestLow = heap.peek().value;
  let bestHigh = maxValue;
  while (true) {
    const smallest = heap.pop();
    if (smallest.nextIndex >= lists[smallest.listIndex].length) {
      break;
    }
    const nextValue = lists[smallest.listIndex][smallest.nextIndex];
    maxValue = Math.max(maxValue, nextValue);
    heap.push({
      value: nextValue,
      listIndex: smallest.listIndex,
      nextIndex: smallest.nextIndex + 1,
    });
    const newMin = heap.peek().value;
    if (maxValue - newMin < bestHigh - bestLow) {
      bestLow = newMin;
      bestHigh = maxValue;
    }
  }
  return [bestLow, bestHigh];
}

Walkthrough

Lists: [4,10,15], [1,9,12], [7,11,18]. Initialize heap with (4,0), (1,1), (7,2) → maxValue=10, min=1 → range 9. Pop 1 from list 1, push 9 → active {4,9,7}, max=10, min=4 → range 6. Continue until a list exhausts; track narrowest range.

Invariant: at each step the heap holds exactly one “pointer” per non-exhausted list; popping the smallest and advancing that list is the only move that can shrink the minimum without missing optimality (exchange argument).

Edge Cases

k == 1 — range is [min(list), min(list)] (single element on each side).
Duplicates across lists — maxValue must track the current window max, not the global max ever seen incorrectly.
One list much longer — algorithm stops when any list runs out during pop (cannot keep one-per-list anymore).

Pitfalls

Initializing bestHigh - bestLow without recording the first full window before any pop.
Using global max over all elements ever inserted instead of current k heads.
Off-by-one on nextIndex when pushing the successor element.

Variants

Smallest range with frequency / multiset — each list contributes multiple picks; problem statement changes feasibility check.
Dynamic lists (streaming append) — rerun from scratch or maintain augmented structure; ask bounded delay vs exact optimum.
Tie-break: smallest bestLow when ranges tie — extend comparison to (range, bestLow) lexicographically.

Mind-Map Tags

#k-way-merge #min-heap #running-max #sorted-lists #smallest-range #greedy-advance-min