002. Running Minimum and Maximum

Why this mechanism works

A new value can change the minimum, the maximum, both on the first step, or neither. These are independent reductions over the same prefix, so one scan can maintain both. Initializing from the first actual value avoids assuming that zero belongs to the data.

State and boundaries

low and high summarize the processed prefix. minimums and maximums contain one committed result per consumed value.

Protocol

1. Return two empty lists when there is no first value.
2. Initialize both extrema from nums[0].
3. Extend both extrema with each incoming value.
4. Append both answers after updating.

Visualization

value:  4  2  5  1
low:    4  2  2  1
high:   4  4  5  5

Python implementation

def running_extrema(nums):
    if not nums:
        return [], []
    low = high = nums[0]
    minimums, maximums = [], []
    for value in nums:
        low = min(low, value)
        high = max(high, value)
        minimums.append(low)
        maximums.append(high)
    return minimums, maximums

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 running_extrema: if not nums:
nums=[4, 2, 5, 1]

L4 running_extrema: low = high = nums[0]
nums=[4, 2, 5, 1]; low=4; high=4

L5 running_extrema: minimums, maximums = [], []
nums=[4, 2, 5, 1]; low=4; high=4; minimums=[]; maximums=[]

L6 running_extrema: for value in nums:
nums=[4, 2, 5, 1]; low=4; high=4; minimums=[]; maximums=[]; value=4

L9 running_extrema: minimums.append(low)
nums=[4, 2, 5, 1]; low=4; high=4; minimums=[4]; maximums=[]; value=4

L10 running_extrema: maximums.append(high)
nums=[4, 2, 5, 1]; low=4; high=4; minimums=[4]; maximums=[4]; value=4

L6 running_extrema: for value in nums:
nums=[4, 2, 5, 1]; low=4; high=4; minimums=[4]; maximums=[4]; value=2

L7 running_extrema: low = min(low, value)
nums=[4, 2, 5, 1]; low=2; high=4; minimums=[4]; maximums=[4]; value=2

... 6 intermediate state changes omitted ...

L6 running_extrema: for value in nums:
nums=[4, 2, 5, 1]; low=2; high=5; minimums=[4, 2, 2]; maximums=[4, 4, 5]; value=1

L7 running_extrema: low = min(low, value)
nums=[4, 2, 5, 1]; low=1; high=5; minimums=[4, 2, 2]; maximums=[4, 4, 5]; value=1

L9 running_extrema: minimums.append(low)
nums=[4, 2, 5, 1]; low=1; high=5; minimums=[4, 2, 2, 1]; maximums=[4, 4, 5]; value=1

L10 running_extrema: maximums.append(high)
nums=[4, 2, 5, 1]; low=1; high=5; minimums=[4, 2, 2, 1]; maximums=[4, 4, 5, 5]; value=1

L2 running_extrema: if not nums:
nums=[]

Why the solution is correct

The first value is both extrema of a singleton prefix. min(low, value) and max(high, value) preserve the definitions when the prefix grows. Appending only after both updates keeps the two output positions aligned.

Time and space

O(n) time; O(1) working state plus O(n) returned storage.

Common mistakes

Initializing low to zero fails on all-positive input. Using elif between independent extrema updates can mishandle initialization or future variants.

Reasoning card

Transfer exercise

Also return the running range high-low, without rescanning any prefix.