Abstract / Summary

Find the smallest range that includes at least one number from each of the k sorted lists.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Hash Table
• Heap (Priority Queue)
• Sliding Window
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “smallest range covering at least one element from each list” problem. It works by maintaining a min-heap that always contains the current candidate element from each sub-list and a variable that tracks the maximum value among those candidates. By iteratively advancing the pointer in the list that contributes the smallest element, the algorithm explores all feasible ranges and records the best one found.

Key Steps

The algorithm begins by initializing the search interval to an extreme range and preparing auxiliary structures.

start, end = 0, 999999
pos = [0] * len(nums)
lower = [(n[0], i) for i, n in enumerate(nums)]
heapify(lower)
upper = max(lower)[0]

pos stores the current index inside each sub-list. lower is a list of tuples (value, list_index) representing the first element of every list; heapify turns it into a min-heap. upper holds the largest value among the current candidates, obtained by a simple max on the initial heap.

The main loop repeatedly extracts the smallest element from the heap, checks whether the interval defined by this smallest value and the current upper improves the best interval, and then attempts to move forward in the list that contributed the smallest element.

while True:
    a = lower[0]
    smallest = a[1]

    if upper - a[0] < end - start:
        start, end = a[0], upper

a is the heap’s root, i.e., the current minimum. If the distance between upper and this minimum is tighter than the best interval recorded so far, the algorithm updates start and end.

Next, the code determines whether the list that supplied the minimum has been exhausted. If it has, the loop terminates because no further complete ranges can be formed.

    if pos[smallest] == len(nums[smallest]) - 1:
        break

If more elements remain, the pointer for that list is advanced, the heap entry is replaced with the next value, and upper is refreshed to reflect any increase.

    pos[smallest] += 1
    heapreplace(lower, (nums[smallest][pos[smallest]], smallest))
    upper = max(upper, nums[smallest][pos[smallest]])

Finally, after the loop ends, the algorithm returns the best interval discovered.

return [start, end]

Edge Cases Handled

The implementation gracefully handles the situation where one of the input sub-lists contains only a single element. In that case, the condition pos[smallest] == len(nums[smallest]) - 1 becomes true immediately after the first extraction, causing the loop to exit without attempting an out-of-bounds access.

When the input consists of a single list, the heap contains exactly one element, upper equals that element, and the loop terminates after the first iteration. The returned range collapses to a zero-length interval covering that sole element, which is the correct answer.

If the lists contain duplicate values, the heap still orders them correctly because the tuple’s first component (the value) determines priority, while the second component (the list index) serves only as a tie-breaker. The algorithm therefore treats equal values as distinct entries and proceeds without ambiguity.

Performance Optimizations

The code leverages a min-heap (heapify, heapreplace) to obtain the current smallest element in constant amortized time, avoiding a full scan of all candidates on each iteration. By keeping upper as a single scalar that is only updated when a larger element is introduced, the algorithm eliminates the need to recompute the maximum across the heap at every step. The use of heapreplace combines a pop and push into a single operation, reducing overhead compared to separate heappop and heappush calls.

The early termination condition-breaking when the list that contributed the smallest element is exhausted-prevents unnecessary iterations once a complete range can no longer be formed, ensuring that the loop runs only as long as a valid interval is possible. This guard eliminates wasted work and contributes to the overall efficiency of the solution.

Imagine having several different shelves of numbered blocks. Each shelf is already lined up in order from smallest to biggest. The goal is to find a small window that covers at least one number from every single shelf.

To do this, look at the very first number on every shelf. Find the smallest one and the biggest one among those. This makes a starting range. Write those two numbers down so they are not forgotten.

Now, take the shelf that held that smallest number and slide it over to peek at the next number in line. Because the new number might be bigger than the current biggest number, check again to see which of the current numbers on display is the biggest.

Calculate the gap between the smallest and the biggest number being looked at. If this gap is smaller than the gap recorded earlier, update the records with these new numbers.

Keep sliding the shelf that has the smallest number forward, one step at a time, looking for a tighter gap. Do this over and over again. If any shelf runs out of numbers, stop the process because there are no more ways to keep every shelf included in the search.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java					Python	TS
	WalkCCC	C++		Java					Python
	leetcode.ca	C++	JS	Java	Rust		Go		Python	TS
	LeetcodeHelp	C++		Java					Python
	Progiez	C++		Java					Python
github	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	linouk23	C++
	ruoru				Rust
	sonugiri1043	C++
	suxrobGM							C#
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
	yuanliu666					Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality