Waiting for a stronger gust

A wind farm records the strongest gust of every hour. The control room wants each hour annotated with how long the wind took to beat it.

The problem

The log holds one gust speed per hour, in kilometres per hour, in chronological order. For each hour, report how many hours pass before a strictly stronger gust is recorded; an equal gust is a repeat, not a rise, and does not count. If no later hour beats it, report 0.

The answer is a waiting time, not a speed, and it is measured to the first stronger hour, not the strongest one.

Input. gusts — the peak gust of each hour, in order.

Output. A list of the same length, where entry i is the smallest d > 0 with gusts[i + d] > gusts[i], or 0 if no such hour exists.

Example.

gusts = [31, 29, 34, 34, 40, 28, 33]  ->  [2, 1, 2, 1, 0, 1, 0]

Hour 0 (31 km/h) waits two hours for the 34. The first 34 must skip the second, which only matches it, and waits two hours for the 40. The 40 is the peak of the day, so it gets 0, and so does the final 33 — the log ends.

A second example, one falling day and one rising day:

gusts = [46, 41, 38, 35]  ->  [0, 0, 0, 0]
gusts = [12, 18, 25]      ->  [1, 1, 0]

A log that only weakens answers nothing; one that only strengthens is answered entirely by the next hour.

Constraints.

• 1 <= len(gusts) <= 10^5
• 0 <= gusts[i] <= 300

Hints

Approach

Brute force

For each hour, scan forward until a stronger gust turns up: O(n²) comparisons, about 5 × 10^9 on a 10^5-hour log, and a steadily weakening day makes every scan run to the end before giving up.

The insight

An hour is still waiting only if every hour since has been no stronger, so the hours in the waiting set are non-increasing in speed — and a new gust settles a solid block of them from the most recent backwards.

That ordering is what makes a stack the right container. Push each hour as it arrives and the stack reads bottom to top as non-increasing speeds: exactly the unbeaten hours. A new gust pops the ones it exceeds, contiguous at the top, and stops at the first hour it cannot beat — everything below that is at least as strong, so none of it is settled either.

Algorithm

1. Start with waits all 0 and an empty stack of hour numbers.
2. For each hour i with speed g, look at the top of the stack.
3. While the gust at the top hour is strictly less than g, pop that hour j and set waits[j] = i - j.
4. Push i.
5. Hours still on the stack at the end were never beaten, and keep their 0.

Complexity

Time O(n) — n pushes and at most n pops, each constant work, however tangled the log. Space O(n) for the stack, which holds every hour when the wind drops all day.

Solution

"""Waiting for a stronger gust — a monotonic stack of hours still unanswered."""


def solve(gusts):
    # Stack invariant: it holds the hours nothing has beaten yet, and their gusts
    # are non-increasing from the bottom up — an hour can only still be waiting if
    # every hour since was no stronger, which is exactly what that ordering says.
    waits = [0] * len(gusts)
    pending = []

    for hour, speed in enumerate(gusts):
        while pending and gusts[pending[-1]] < speed:   # strictly stronger settles it
            settled = pending.pop()
            waits[settled] = hour - settled
        pending.append(hour)

    return waits                                        # hours never beaten keep their 0

TESTS = [
    (([31, 29, 34, 34, 40, 28, 33],), [2, 1, 2, 1, 0, 1, 0]),
    (([46, 41, 38, 35],), [0, 0, 0, 0]),
    (([12, 18, 25],), [1, 1, 0]),
    # A flat log: equal is not stronger, so nothing is ever settled.
    (([22, 22, 22],), [0, 0, 0]),
    # One hour has no future to wait for.
    (([55],), [0]),
    # A dip that is answered later than the hour after it.
    (([9, 4, 5, 3, 6],), [0, 1, 2, 1, 0]),
]

Pitfalls

• Popping on <= rather than <. An equal gust is not a stronger one; on [31, 29, 34, 34, 40, 28, 33] the first 34 would report a wait of 1 hour instead of 2, pointing at an hour that merely matched it.
• Storing speeds on the stack instead of hour numbers. Speeds tell you that an hour has been beaten but not when it arrived, and the answer is i - j.
• Writing the answer at the arriving hour i instead of the popped hour j. Every entry then describes the hour that did the settling: the rising log [12, 18, 25] comes back as [0, 1, 1] rather than [1, 1, 0].

Variants

• The next lot to beat it — the same waiting set, scanned backwards and answered with a value rather than a delay.
• Banner across the silos — a pop that needs the position underneath as well as the arriving one.