Daily Temperatures

Given a list of daily temperatures, for each day return how many days you'd have to wait until a warmer day. If there's no future warmer day, the answer for that day is 0.

Example

Input: 73 74 75 71 69 72 76 73 Output: 1 1 4 2 1 1 0 0

Approach

A brute-force scan-ahead for every day is O(n²). Instead, keep a stack of indices whose temperatures are still waiting for a warmer day, kept in decreasing order of temperature. When today's temperature beats the temperature at the top of the stack, that's the warmer day that index was waiting for — pop it and record the day gap, then keep popping while today still beats the new top. Push today's index last. Every index is pushed once and popped at most once, so the whole scan is O(n).

Walkthrough

1def daily_temperatures(temps):
2    n = len(temps)
3    answer = [0] * n
4    stack = []  # indices, decreasing temps
5    for i, t in enumerate(temps):
6        while stack and temps[stack[-1]] < t:
7            j = stack.pop()
8            answer[j] = i - j
9        stack.append(i)
10    return answer

Input format

Line 1: the array, space-separated

Print the answer array, space-separated.