How many days until a warmer day?

Keep a stack of days still waiting for a warmer day; their temperatures decrease from bottom to top. For each new day, pop every waiting day that is colder and record the gap, then push the new day. Each day is pushed and popped at most once: O(n) time, O(n) space.

This is the monotonic stack pattern: the stack stays sorted, and each pop answers a question.

Checking every later day for each day is O(n²).

Walking from the right with a stack of candidates works too.

def wait_for_warmer(temps: list[int]) -> list[int]:
    wait = [0] * len(temps)
    pending: list[int] = []  # days still waiting, colder at the top
    for day, t in enumerate(temps):
        while pending and temps[pending[-1]] < t:
            earlier = pending.pop()
            wait[earlier] = day - earlier
        pending.append(day)
    return wait

fun waitForWarmer(temps: List<Int>): List<Int> {
    val wait = MutableList(temps.size) { 0 }
    val pending = ArrayDeque<Int>()
    for ((day, t) in temps.withIndex()) {
        while (pending.isNotEmpty() && temps[pending.last()] < t) {
            val earlier = pending.removeLast()
            wait[earlier] = day - earlier
        }
        pending.addLast(day)
    }
    return wait
}

Common mistakes

• Popping with <= so equal temperatures count as warmer.
• Storing temperatures instead of indices, which loses the gap.

Explain why each day is popped at most once; it is the O(n) proof.

Follow-up questions

Think of your answer first, then open the hint.

1. What about the next colder day?

   Show hint

   Flip the comparison so the stack keeps increasing temperatures.

2. How would you handle a circular week?

   Show hint

   Walk the list twice (indices mod n) so the end can see the start.