TheAlgorithms-Python

1
"""
2
smallest_range function takes a list of sorted integer lists and finds the smallest
3
range that includes at least one number from each list, using a min heap for efficiency.
4
"""
5

6
from heapq import heappop, heappush
7
from sys import maxsize
8

9

10
def smallest_range(nums: list[list[int]]) -> list[int]:
11
    """
12
    Find the smallest range from each list in nums.
13

14
    Uses min heap for efficiency. The range includes at least one number from each list.
15

16
    Args:
17
        nums: List of k sorted integer lists.
18

19
    Returns:
20
        list: Smallest range as a two-element list.
21

22
    Examples:
23
    >>> smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]])
24
    [20, 24]
25
    >>> smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]])
26
    [1, 1]
27
    >>> smallest_range(((1, 2, 3), (1, 2, 3), (1, 2, 3)))
28
    [1, 1]
29
    >>> smallest_range(((-3, -2, -1), (0, 0, 0), (1, 2, 3)))
30
    [-1, 1]
31
    >>> smallest_range([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
32
    [3, 7]
33
    >>> smallest_range([[0, 0, 0], [0, 0, 0], [0, 0, 0]])
34
    [0, 0]
35
    >>> smallest_range([[], [], []])
36
    Traceback (most recent call last):
37
        ...
38
    IndexError: list index out of range
39
    """
40

41
    min_heap: list[tuple[int, int, int]] = []
42
    current_max = -maxsize - 1
43

44
    for i, items in enumerate(nums):
45
        heappush(min_heap, (items[0], i, 0))
46
        current_max = max(current_max, items[0])
47

48
    # Initialize smallest_range with large integer values
49
    smallest_range = [-maxsize - 1, maxsize]
50

51
    while min_heap:
52
        current_min, list_index, element_index = heappop(min_heap)
53

54
        if current_max - current_min < smallest_range[1] - smallest_range[0]:
55
            smallest_range = [current_min, current_max]
56

57
        if element_index == len(nums[list_index]) - 1:
58
            break
59

60
        next_element = nums[list_index][element_index + 1]
61
        heappush(min_heap, (next_element, list_index, element_index + 1))
62
        current_max = max(current_max, next_element)
63

64
    return smallest_range
65

66

67
if __name__ == "__main__":
68
    from doctest import testmod
69

70
    testmod()
71
    print(f"{smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]])}")  # Output: [1, 1]
72