How Many Days Until the River Rises Above Today's Level

Scanning forward from every day reads the same low days again and again; a stack of waiting days answers each one when the rise arrives.

A monotonic stack of indices finds how far each position waits for a larger value in O(n), because every index is pushed once and popped at most once. A gauge on a river recorded its level in centimetres each day for a week, 30 32 31 29 33 35 34, and the question for each day is how many days pass until the level is higher than that day's, or 0 if it never is.

The brute force scans forward from each day until it finds a higher level. On levels that only fall, every scan reads to the end, so the cost is O(n²) for n days. The repeated work is that low days are read again by every earlier day's scan: day 3 is read by the scans from days 0, 1 and 2.

The stack keeps the days still waiting, their levels decreasing towards the top. The answer is a distance, so the stack holds days, not levels: when day i pops a waiting day w, the answer for w is i − w, and its level is one read away as levels[w].

Scanning forward against a stack of waiting days

ScanningO(n²) time

For each day, read the later days one by one until a higher level appears. A falling stretch is read again by every day before it.

Stack of daysO(n) time

Each day pops every waiting day with a lower level and records the distance, then waits itself. Every day is pushed once and popped at most once.

The inner loop sometimes pops several days at once, which looks like O(n²). An instrumented run counts the pushes and pops:

Pushes and pops over the levels 30 32 31 29 33 35 34, from an instrumented run
Day	Level	Popped on this day	Pushes so far	Pops so far
0	30	none	1	0
1	32	0	2	1
2	31	none	3	1
3	29	none	4	1
4	33	3, 2 and 1	5	4
5	35	4	6	5
6	34	none	7	5

Day 4 popped three days, but each of those days was popped once in the whole pass and never again. Pops can never outnumber pushes, and there are n pushes, so the inner loop runs at most n times in all, and the pass is O(n) time with O(n) extra space for the stack. The listing runs both versions.

river.pypy

def days_by_scanning(levels: list[int]) -> list[int]:
    answer = [0] * len(levels)
    for day in range(len(levels)):
        for later in range(day + 1, len(levels)):
            if levels[later] > levels[day]:
                answer[day] = later - day
                break
    return answer


def days_by_stack(levels: list[int]) -> tuple[list[int], int, int]:
    answer = [0] * len(levels)
    stack: list[int] = []
    pushes = pops = 0
    for day, level in enumerate(levels):
        while stack and levels[stack[-1]] < level:
            waiting = stack.pop()
            answer[waiting] = day - waiting
            pops += 1
        stack.append(day)
        pushes += 1
    return answer, pushes, pops


levels = [30, 32, 31, 29, 33, 35, 34]
print("scanning:", *days_by_scanning(levels))
answer, pushes, pops = days_by_stack(levels)
print("stack:   ", *answer, f"({pushes} pushes, {pops} pops)")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

scanning: 1 3 2 1 1 0 0
stack:    1 3 2 1 1 0 0 (7 pushes, 5 pops)

Both give 1 3 2 1 1 0 0, and the stack made 7 pushes and 5 pops for 7 days. Days 5 and 6 were never popped, so their answer stays 0. Counting the total work of a loop across the whole run, rather than its worst single step, is called amortised analysis.

Stacks and Queues

← → move through sections and cards