Practice: Waiting for a Cheaper Fare

Daily fares for a week: for each day, how many days until a strictly cheaper fare, and why the whole pass is O(n).

Adapting the monotonic stack to the next smaller value means reversing its comparison and keeping everything else. A traveller watched the cheapest train fare in pounds each day for a week: 9 7 8 7 5 6 4. For each day, find how many days pass until a strictly cheaper fare, or 0 if none comes. Say what the stack holds and in what order, and why the pass is O(n) though its inner loop can pop several days at once.

Show the answers and a solution

The waits are 1 3 1 1 2 1 0. The answer is a distance, so the stack holds days, and it pops a waiting day when today's fare is lower, so the waiting fares increase from bottom to top. Strictly cheaper means a fare equal to a waiting one does not pop it: the second 7, on day 3, leaves day 1 waiting until the 5 on day 4. The trace prints the stack and the answers after each day, with a blank for a day still waiting.

text

--- day 0, fare 9
9 7 8 7 5 6 4
^
stack (indices): 0
answer: _ _ _ _ _ _ _
--- day 1, fare 7
9 7 8 7 5 6 4
  ^
stack (indices): 1
answer: 1 _ _ _ _ _ _
--- day 2, fare 8
9 7 8 7 5 6 4
    ^
stack (indices): 1 2
answer: 1 _ _ _ _ _ _
--- day 3, fare 7
9 7 8 7 5 6 4
      ^
stack (indices): 1 3
answer: 1 _ 1 _ _ _ _
--- day 4, fare 5
9 7 8 7 5 6 4
        ^
stack (indices): 4
answer: 1 3 1 1 _ _ _
--- day 5, fare 6
9 7 8 7 5 6 4
          ^
stack (indices): 4 5
answer: 1 3 1 1 _ _ _
--- day 6, fare 4
9 7 8 7 5 6 4
            ^
stack (indices): 6
answer: 1 3 1 1 2 1 _
days until a cheaper fare: 1 3 1 1 2 1 0

The listing runs the same pass on the week and on fares that only rise.

cheaper_fare.pypy

def days_until_cheaper(fares: list[int]) -> list[int]:
    answer = [0] * len(fares)
    stack: list[int] = []
    for day, fare in enumerate(fares):
        while stack and fares[stack[-1]] > fare:
            waiting = stack.pop()
            answer[waiting] = day - waiting
        stack.append(day)
    return answer


print("days until a cheaper fare:", *days_until_cheaper([9, 7, 8, 7, 5, 6, 4]))
print("rising fares:", *days_until_cheaper([3, 4, 5]))

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

days until a cheaper fare: 1 3 1 1 2 1 0
rising fares: 0 0 0

Every day is pushed once and popped at most once, so all the pops together number at most n, and the pass is O(n) time and O(n) extra space for n days. On rising fares nothing is popped and every wait is 0.

Stacks and Queues

← → move through sections and cards