LeetCode 632 - Smallest Range Covering Elements from K Lists

LeetCode Problem 632

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Greedy, Sliding Window, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us k sorted integer lists, and we must find the smallest inclusive range [a, b] such that the range contains at least one element from every list.

Each list is already sorted in non-decreasing order, which is a very important property. Instead of considering arbitrary combinations of elements, we can take advantage of the ordering to efficiently move through the lists.

The output is not a single number, but a range represented as a two-element array [start, end]. A range is considered "smaller" if its width is smaller. Formally, [a, b] is better than [c, d] if:

• b - a < d - c
• or the widths are equal and a < c

This second condition means that if two ranges have the same size, we prefer the one that starts earlier.

The constraints are large enough that brute force enumeration becomes impractical:

• Up to 3500 lists
• Each list can contain up to 50 elements
• Total elements can therefore reach 175,000

A naive approach that tries every possible combination across all lists would explode combinatorially.

There are several important edge cases:

• Multiple lists may contain identical values, which means the answer could be a zero-width range like [1,1].
• Lists can contain negative numbers.
• Lists may have very different lengths.
• Some lists may contain only one element.
• The optimal range may appear near the end of the traversal, so stopping early is unsafe unless one list is exhausted.

The problem guarantees that every list is non-empty and sorted, which makes heap-based techniques especially effective.

Approaches

Brute Force Approach

The brute force idea is to consider every possible selection where we choose one element from each list. For every combination, we compute the minimum and maximum selected values, which defines a candidate range. We then keep the smallest range encountered.

This approach is correct because every valid answer corresponds to at least one such combination.

However, the number of combinations is enormous. If each list contains approximately m elements and there are k lists, then the total number of combinations is roughly:

$$m^k$$

Even with small values, this becomes computationally impossible.

Another slightly improved brute force strategy is to flatten all numbers, sort them, and then test ranges repeatedly, but without an efficient way to maintain coverage across all lists, this still becomes too slow.

Key Insight

The key observation is that we only need to track one active element from each list at any time.

Suppose we currently have one selected number from every list. The smallest selected number defines the left boundary of the current range, while the largest selected number defines the right boundary.

If we want to potentially improve the range, the only useful move is to advance the list containing the current minimum value.

Why?

Because the current minimum determines the left boundary. Moving any other pointer would only increase or preserve the maximum value while leaving the minimum unchanged, which cannot shrink the range.

This naturally leads to a min-heap solution:

• Store one active element from each list in a min-heap
• Track the current maximum separately
• Repeatedly remove the minimum element
• Advance that list to its next value
• Update the best range seen so far

This guarantees that we always maintain coverage from all lists while efficiently exploring candidate ranges.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m^k)	O(k)	Tries every possible combination of one element per list
Optimal	O(N log k)	O(k)	Uses a min-heap to maintain one active element from each list

Here, N is the total number of elements across all lists.

Algorithm Walkthrough

Optimal Heap-Based Algorithm

1. Initialize a min-heap with the first element from every list.

Each heap entry stores:

• the value
• the index of the list it came from
• the index within that list

This guarantees that the heap always contains exactly one active element from every list. 2. Track the current maximum value among all active elements.

The heap gives us the minimum element efficiently, but we also need the maximum to define the current candidate range. 3. Initialize the best answer using the initial heap state.

The current range is:

$$[\text{heap minimum}, \text{current maximum}]$$ 4. Repeatedly pop the minimum element from the heap.

This minimum element defines the current left boundary of the range. 5. Compare the current range against the best range found so far.

Update the answer if:

• the current range is smaller
• or the widths are equal and the current start is smaller

6. Advance the list that contributed the minimum element.

This is the critical greedy step.

Since the minimum element limits how small the range can be, the only possible way to improve the range is to move that list forward. 7. If the list has no more elements, stop the algorithm.

At this point, we can no longer maintain coverage from all lists, because one list is exhausted. 8. Otherwise, push the next element from that list into the heap.

Update the current maximum if necessary. 9. Continue until termination.

Why it works

The algorithm maintains an invariant:

• The heap always contains exactly one active element from every list.

Therefore, every heap state corresponds to a valid range covering all lists.

At each step, the smallest active element determines the left boundary. Any better range must increase this minimum, because leaving it unchanged cannot shrink the interval. Advancing the list that owns the minimum is therefore the only productive move.

Since every valid candidate generated by this progression is examined, and we always keep the smallest range encountered, the final answer is optimal.

Python Solution

from typing import List
import heapq

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        min_heap = []
        current_max = float("-inf")

        # Initialize heap with first element from each list
        for list_index, values in enumerate(nums):
            value = values[0]
            heapq.heappush(min_heap, (value, list_index, 0))
            current_max = max(current_max, value)

        best_start = min_heap[0][0]
        best_end = current_max

        while True:
            current_min, list_index, element_index = heapq.heappop(min_heap)

            # Update best range if current one is better
            if (
                current_max - current_min < best_end - best_start
                or (
                    current_max - current_min == best_end - best_start
                    and current_min < best_start
                )
            ):
                best_start = current_min
                best_end = current_max

            # Move to next element in the same list
            next_index = element_index + 1

            # Cannot maintain coverage anymore
            if next_index == len(nums[list_index]):
                break

            next_value = nums[list_index][next_index]

            heapq.heappush(
                min_heap,
                (next_value, list_index, next_index)
            )

            current_max = max(current_max, next_value)

        return [best_start, best_end]

The implementation begins by inserting the first element from every list into the heap. This creates the initial valid range because we immediately have one element from each list.

The heap stores tuples of:

• value
• list index
• element index

The tuple structure allows us to identify exactly which list contributed the minimum element after each pop operation.

current_max is maintained separately because a min-heap only gives direct access to the smallest value. Together, the heap minimum and current_max define the current candidate interval.

Inside the loop, we pop the minimum element and compare the resulting range against the best answer. Then we attempt to advance within the same list.

If that list is exhausted, the algorithm terminates because it is impossible to continue forming valid ranges containing all lists.

Otherwise, the next element is pushed into the heap, and current_max is updated if needed.

The process continues until one list runs out of elements.

Go Solution

package main

import (
	"container/heap"
)

type Node struct {
	value      int
	listIndex  int
	valueIndex int
}

type MinHeap []Node

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].value < h[j].value
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func smallestRange(nums [][]int) []int {
	minHeap := &MinHeap{}
	heap.Init(minHeap)

	currentMax := -100001

	// Initialize heap
	for listIndex, values := range nums {
		value := values[0]

		heap.Push(minHeap, Node{
			value:      value,
			listIndex:  listIndex,
			valueIndex: 0,
		})

		if value > currentMax {
			currentMax = value
		}
	}

	bestStart := (*minHeap)[0].value
	bestEnd := currentMax

	for {
		current := heap.Pop(minHeap).(Node)

		currentMin := current.value

		// Update best range
		if currentMax-currentMin < bestEnd-bestStart ||
			(currentMax-currentMin == bestEnd-bestStart &&
				currentMin < bestStart) {

			bestStart = currentMin
			bestEnd = currentMax
		}

		nextIndex := current.valueIndex + 1

		// Cannot continue coverage
		if nextIndex == len(nums[current.listIndex]) {
			break
		}

		nextValue := nums[current.listIndex][nextIndex]

		heap.Push(minHeap, Node{
			value:      nextValue,
			listIndex:  current.listIndex,
			valueIndex: nextIndex,
		})

		if nextValue > currentMax {
			currentMax = nextValue
		}
	}

	return []int{bestStart, bestEnd}
}

The Go implementation follows the same logic as the Python solution but requires a custom heap implementation using the container/heap package.

A Node struct stores the current value and its position information. The MinHeap type implements the required heap interface methods.

Unlike Python's built-in heapq, Go's heap implementation uses interface methods and explicit type assertions.

Go does not have negative infinity for integers, so currentMax is initialized using a value smaller than the minimum possible constraint.

Worked Examples

Example 1

Input:

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

Initial heap state:

Heap Values	Current Max	Range
0, 4, 5	5	[0,5]

We now repeatedly pop the minimum.

Step	Popped	Inserted	Heap Values	Current Max	Best Range
1	0	9	4,5,9	9	[0,5]
2	4	10	5,9,10	10	[0,5]
3	5	18	9,10,18	18	[0,5]
4	9	12	10,12,18	18	[0,5]
5	10	15	12,15,18	18	[0,5]
6	12	20	15,18,20	20	[0,5]
7	15	24	18,20,24	24	[0,5]
8	18	22	20,22,24	24	[20,24]

At step 8:

• minimum = 20
• maximum = 24
• width = 4

This becomes the new best range.

Continuing further cannot produce a smaller valid range before exhaustion occurs.

Final answer:

[20,24]

Example 2

Input:

[[1,2,3],
 [1,2,3],
 [1,2,3]]

Initial heap:

Heap Values	Current Max	Range
1,1,1	1	[1,1]

Immediately, the algorithm finds a zero-width range covering all lists.

Since no range can be smaller than width 0, this is already optimal.

Final answer:

[1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N log k)	Each element is inserted and removed from the heap once
Space	O(k)	The heap stores at most one active element per list

Here:

• N is the total number of elements across all lists
• k is the number of lists

Each heap operation costs O(log k) because the heap size never exceeds k. Since every element is processed at most once, the total complexity becomes O(N log k).

The space complexity is O(k) because the heap contains one active element from each list at all times.

Test Cases

from typing import List

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        import heapq

        min_heap = []
        current_max = float("-inf")

        for list_index, values in enumerate(nums):
            value = values[0]
            heapq.heappush(min_heap, (value, list_index, 0))
            current_max = max(current_max, value)

        best_start = min_heap[0][0]
        best_end = current_max

        while True:
            current_min, list_index, element_index = heapq.heappop(min_heap)

            if (
                current_max - current_min < best_end - best_start
                or (
                    current_max - current_min == best_end - best_start
                    and current_min < best_start
                )
            ):
                best_start = current_min
                best_end = current_max

            next_index = element_index + 1

            if next_index == len(nums[list_index]):
                break

            next_value = nums[list_index][next_index]

            heapq.heappush(
                min_heap,
                (next_value, list_index, next_index)
            )

            current_max = max(current_max, next_value)

        return [best_start, best_end]

solution = Solution()

assert solution.smallestRange(
    [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
) == [20,24]  # official example

assert solution.smallestRange(
    [[1,2,3],[1,2,3],[1,2,3]]
) == [1,1]  # identical lists

assert solution.smallestRange(
    [[1],[2],[3]]
) == [1,3]  # single element lists

assert solution.smallestRange(
    [[-5,-4,-3],[-2,-1],[0]]
) == [-3,0]  # negative numbers

assert solution.smallestRange(
    [[1,5,8],[4,12],[7,8,10]]
) == [4,7]  # mixed overlaps

assert solution.smallestRange(
    [[1,9],[4,12],[7,10,16]]
) == [9,12]  # optimal range near end

assert solution.smallestRange(
    [[1,2,3,4],[2,3,4,5],[3,4,5,6]]
) == [3,3]  # exact overlap

assert solution.smallestRange(
    [[1,100],[50],[75]]
) == [50,100]  # sparse distribution

Test	Why
Official example	Validates standard overlapping behavior
Identical lists	Ensures zero-width range works
Single element lists	Tests minimal list sizes
Negative numbers	Ensures ordering logic handles negatives
Mixed overlaps	Tests intermediate optimal ranges
Optimal range near end	Verifies algorithm does not stop early
Exact overlap	Confirms perfect intersection handling
Sparse distribution	Tests wide ranges

Edge Cases

One important edge case occurs when all lists share the same value. For example:

[[1,2],[1,3],[1,4]]

The optimal answer is [1,1]. Some incorrect implementations fail to recognize that a zero-width interval is valid. This implementation correctly handles the case because it continuously compares interval widths and allows equal endpoints.

Another important case involves lists containing negative numbers. Since ranges depend only on relative ordering, negative values must be processed exactly like positive values. The heap ordering naturally handles this without special logic. Initializing currentMax carefully ensures correctness even when all values are negative.

A third critical edge case occurs when one list is extremely short. For example:

[[1],[2,3,4],[5,6]]

Once the single-element list is exhausted, no further valid ranges are possible. The algorithm explicitly stops when any list runs out of elements, preventing invalid intervals that fail to include all lists.

A fourth subtle case involves tie-breaking. Consider two ranges with identical width:

[1,3]
[2,4]

Both have width 2, but [1,3] is preferred because its start is smaller. The implementation handles this with the secondary comparison condition:

current_min < best_start

This guarantees compliance with the problem's exact ordering rules.