# LeetCode 632: Smallest Range Covering Elements from K Lists

## Problem Restatement

We are given `k` sorted lists of integers.

We need to find the smallest range `[a, b]` such that the range contains at least one number from every list.

A number `x` is inside the range `[a, b]` if:

```python
a <= x <= b
```

A range `[a, b]` is smaller than another range `[c, d]` if:

```text
b - a < d - c
```

If both ranges have the same length, choose the one with the smaller start value `a`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums`, a list of `k` sorted integer lists |
| Output | The smallest valid range `[a, b]` |
| Valid range | Must include at least one number from every list |
| Tie-break | Smaller start value wins when lengths are equal |

Constraints:

| Constraint | Value |
|---|---|
| `nums.length == k` | `1 <= k <= 3500` |
| `nums[i].length` | `1 <= nums[i].length <= 50` |
| `nums[i][j]` | `-10^5 <= nums[i][j] <= 10^5` |
| Order | Each `nums[i]` is sorted in non-decreasing order |

## Examples

Example 1:

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

The answer is:

```python
[20, 24]
```

Why?

| List | Number inside `[20, 24]` |
|---|---:|
| `[4, 10, 15, 24, 26]` | `24` |
| `[0, 9, 12, 20]` | `20` |
| `[5, 18, 22, 30]` | `22` |

So `[20, 24]` covers all three lists.

Example 2:

```python
nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
```

The answer is:

```python
[1, 1]
```

The range `[1, 1]` contains `1` from every list.

## First Thought: Check All Ranges

A direct idea is to consider every possible pair `[a, b]` from all numbers in all lists.

For each range, check whether it contains at least one value from each list.

This works, but it is too slow.

Let `N` be the total number of values across all lists. There can be many candidate ranges, and checking each range against all lists is expensive.

We need to exploit the fact that each list is already sorted.

## Key Insight

At any moment, suppose we choose one current number from each list.

Then those `k` numbers define a valid range:

```text
minimum chosen value to maximum chosen value
```

For example, if the current chosen values are:

```python
4, 0, 5
```

then the current range is:

```python
[0, 5]
```

This range covers all lists because it was built from one number from each list.

To improve the range, we should move the list that currently has the minimum value.

Why?

The current maximum value already fixes the right side of the range. If we move any list other than the minimum one, the minimum stays the same, so the range cannot get smaller. The only way to possibly increase the left boundary and shrink the range is to advance the list that owns the current minimum.

This is a k-way merge idea.

We use a min-heap to find the current minimum efficiently, and we keep a variable `current_max` for the current maximum.

## Algorithm

1. Put the first element of every list into a min-heap.
2. Track the maximum value among these first elements.
3. The heap minimum and `current_max` form a valid range.
4. Pop the minimum value from the heap.
5. Advance in the same list from which that minimum came.
6. Push the next value from that list into the heap.
7. Update `current_max`.
8. Repeat until one list has no next value.

When one list is exhausted, we stop. After that point, we can no longer form a range that includes every list.

## Implementation

```python
import heapq

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

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

        best_start = heap[0][0]
        best_end = current_max

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

            if current_max - current_min < best_end - 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(heap, (next_value, list_index, next_index))
            current_max = max(current_max, next_value)

        return [best_start, best_end]
```

## Code Explanation

The heap stores triples:

```python
(value, list_index, element_index)
```

This tells us:

| Field | Meaning |
|---|---|
| `value` | The actual number |
| `list_index` | Which list it came from |
| `element_index` | Its position inside that list |

We initialize the heap with the first value from each list:

```python
for list_index, arr in enumerate(nums):
    value = arr[0]
    heapq.heappush(heap, (value, list_index, 0))
    current_max = max(current_max, value)
```

At this point, the heap has one value from every list, so it defines a valid range.

The smallest current value is at the top of the heap:

```python
current_min, list_index, element_index = heapq.heappop(heap)
```

The current range is:

```python
[current_min, current_max]
```

If this range is smaller than the best known range, we update the answer:

```python
if current_max - current_min < best_end - best_start:
    best_start = current_min
    best_end = current_max
```

When lengths are equal, we do not update. Since the process sees ranges in increasing left-bound order, keeping the earlier range preserves the smaller start tie-break.

Then we advance in the same list:

```python
next_index = element_index + 1
```

If that list is exhausted, we stop:

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

Otherwise, we push the next value and update `current_max`:

```python
next_value = nums[list_index][next_index]
heapq.heappush(heap, (next_value, list_index, next_index))
current_max = max(current_max, next_value)
```

## Correctness

At every iteration, the heap contains exactly one chosen element from each list. Therefore, the interval from the heap minimum to `current_max` contains at least one element from every list, so it is a valid range.

Consider the current range `[current_min, current_max]`. The left endpoint comes from the list at the top of the heap. If we do not advance this list, then the minimum chosen value remains `current_min`. Advancing any other list cannot increase the left endpoint, so it cannot produce a smaller range with the current choices.

Therefore, the only useful next move is to advance the list that owns the current minimum.

The algorithm repeatedly performs exactly this move. Since each list is sorted, advancing a list moves its chosen value forward in non-decreasing order. This enumerates all candidate ranges that can be optimal under the k-way merge process.

Whenever a valid range is seen, the algorithm compares it with the best known range and keeps the smaller one. If the length is equal, it keeps the earlier start value.

When some list is exhausted, no future range can include an element from every list, because that list has no remaining candidate to choose. So stopping is correct.

Thus the returned range is the smallest valid range.

## Complexity

Let `N` be the total number of elements across all lists, and let `k` be the number of lists.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(N log k)` | Each element is pushed and popped at most once, and heap size is `k` |
| Space | `O(k)` | The heap stores one element from each list |

## Alternative Solution: Merge Then Sliding Window

Another way is to flatten all numbers into one array while remembering which list each number came from.

Then sort that array and use a sliding window to find the smallest window that contains all `k` list IDs.

```python
from collections import defaultdict

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        merged = []

        for list_index, arr in enumerate(nums):
            for value in arr:
                merged.append((value, list_index))

        merged.sort()

        count = defaultdict(int)
        covered = 0
        left = 0

        best_start = -10**9
        best_end = 10**9

        for right, (right_value, right_list) in enumerate(merged):
            if count[right_list] == 0:
                covered += 1
            count[right_list] += 1

            while covered == len(nums):
                left_value, left_list = merged[left]

                if right_value - left_value < best_end - best_start:
                    best_start = left_value
                    best_end = right_value

                count[left_list] -= 1
                if count[left_list] == 0:
                    covered -= 1

                left += 1

        return [best_start, best_end]
```

This solution is also correct, but it uses more memory because it stores all values.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(N log N)` | Sorting all values dominates |
| Space | `O(N)` | The merged list stores all values |

## Testing

```python
def run_tests():
    s = Solution()

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

    assert s.smallestRange([
        [1, 2, 3],
        [1, 2, 3],
        [1, 2, 3],
    ]) == [1, 1]

    assert s.smallestRange([
        [1],
        [2],
        [3],
    ]) == [1, 3]

    assert s.smallestRange([
        [-5, -4],
        [-3, -2],
        [-1],
    ]) == [-5, -1]

    assert s.smallestRange([
        [1, 5, 8],
        [4, 12],
        [7, 8, 10],
    ]) == [4, 7]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official multi-list example | Checks normal behavior |
| Same values in every list | Best range can have length `0` |
| One value per list | Must use all values |
| Negative values | Confirms range logic with negatives |
| Overlapping lists | Checks heap advancement logic |