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