Glasshouse spread

A nursery glasshouse logs its air temperature once a minute through the night. The grower does not care about the readings themselves — she cares how far they have drifted apart.

The problem

readings[i] is the temperature at minute i in tenths of a degree Celsius, so 118 means 11.8 °C and -40 means −4.0 °C. Negatives are normal on a clear night.

For every minute, report the spread so far: the difference between the warmest and the coldest reading logged up to and including that minute. A spread that jumps means the vent motors overshot, and the grower reads the output beside the log to find the minute it happened.

The answer holds one number per reading, in the same order. Minute 0 always reports 0, because one reading is both the warmest and the coldest.

Input. readings — a list of integers, tenths of a degree, in time order.

Output. A list of the same length; entry i is max(readings[0..i]) - min(readings[0..i]).

Example.

readings = [118, 121, 117, 130, 112]  ->  [0, 3, 4, 13, 18]

The warmest so far runs 118, 121, 121, 130, 130 and the coldest runs 118, 118, 117, 117, 112. Minute 3 raises the ceiling, minute 4 drops the floor, and each widens the spread.

A second example, a night the vents held:

readings = [95, 95, 95]  ->  [0, 0, 0]

Equal readings move neither extreme. Note that the output never shrinks: a spread once recorded cannot be undone by a later reading.

Constraints.

• 0 <= len(readings) <= 10^5, and an empty log returns an empty list
• -500 <= readings[i] <= 600

Hints

Approach

Brute force

For each minute, scan the readings up to it for the maximum and the minimum: 2 · (1 + 2 + … + n) comparisons, about n² in total — around 10¹⁰ at 10⁵ readings, recomputing the same prefix over and over.

The insight

A prefix only grows, so its extremes can be beaten but never invalidated — each new reading updates one running value and leaves the other alone.

Nothing is ever removed here: minute i + 1 sees every reading minute i saw, plus one. The warmest so far stays the warmest unless the new reading beats it, and the same holds at the cold end, so two carried numbers describe the prefix exactly. That is the precondition worth naming, and it fails the moment readings leave from the left, as in a sliding window: the value being dropped might be the extreme, and one number no longer reconstructs the rest.

Algorithm

1. If the log is empty, return an empty list.
2. Set hottest and coldest to readings[0], and start the output with 0.
3. For each later reading, raise hottest or lower coldest as needed.
4. Append hottest - coldest.
5. Return the output list.

Complexity

Time O(n) — two comparisons and a subtraction per minute. Space O(n) for the output the answer requires, and O(1) beyond it.

Solution

"""Glasshouse spread — running maximum and minimum in a single scan."""


def solve(readings):
    if not readings:
        return []
    hottest = coldest = readings[0]
    spreads = [0]
    for reading in readings[1:]:
        # invariant: a prefix only grows, so an extreme can be beaten but never
        # invalidated, and one reading can move at most one of the two.
        if reading > hottest:
            hottest = reading
        elif reading < coldest:
            coldest = reading
        spreads.append(hottest - coldest)
    return spreads

TESTS = [
    (([118, 121, 117, 130, 112],), [0, 3, 4, 13, 18]),
    (([95, 95, 95],), [0, 0, 0]),
    (([-15, -40, -22],), [0, 25, 25]),
    (([204],), [0]),
    (([],), []),
    (([600, -500],), [0, 1100]),
]

Pitfalls

• Seeding hottest and coldest at 0. On a frost log like [-15, -40, -22] the phantom zero reading becomes the ceiling, and the output reads [15, 40, 40] instead of [0, 25, 25]. Seed both from readings[0].
• Appending the spread before updating the extremes. Every entry then lags one minute: the example yields [0, 0, 3, 4, 13], which lines up against the wrong minutes in the log.
• Emitting a value only when the spread changes. The spread is non-decreasing, so a compressed list looks plausible, but [95, 95, 95] then returns [0] and nothing can be matched to a timestamp.

Variants

• The scrap copper spread — one running extreme instead of two, and the difference must be taken in a fixed direction, which is what makes 0 the floor there and not here.
• Empty pockets to the tail — a one-pass scan whose carried state is an index rather than a value.