Daily Temperatures Problem

For each day you need to know how many days pass before a strictly warmer one appears. Keep a stack of the indices whose answer is still unknown, ordered by decreasing temperature. When a new day is warmer than the day on top of the stack, that warmer day is the answer for the popped index, and the difference in indices is the number of days waited.

def daily_temperatures(temps):
    result = [0] * len(temps)
    stack = []
    for i, temp in enumerate(temps):
        while stack and temps[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result


print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print(daily_temperatures([30, 40, 50, 60]))

The outputs are 1, 1, 4, 2, 1, 1, 0, 0 and 1, 1, 1, 0. The 75 at index two has to wait four days for the 76 at index six, and the last two days never see a warmer one so they get zero.

The mechanism is the same decreasing stack used for the next greater element, with the answer being the difference in positions rather than the value itself. The strict comparison matters: equal temperatures do not count as warmer, so a run of equal values stays on the stack until something strictly higher arrives.

The trade-off to name is that the stack version needs random access to the temperatures by index, so it works on an array but not directly on a stream of temperatures arriving one at a time. For a stream you would either keep the stack of values and indices together, which is still linear, or accept that a later warmer day resolves several pending indices at once. The complexity is linear because every index is pushed once and popped at most once, so the amortised cost per day is constant.

For each day, walk forward through the later days and stop at the first one that is strictly warmer. The distance between the two indices is the number of days you waited, and zero means no warmer day ever arrived.

def daily_temperatures(temps):
    result = []
    for i in range(len(temps)):
        days = 0
        for j in range(i + 1, len(temps)):
            if temps[j] > temps[i]:
                days = j - i
                break
        result.append(days)
    return result


print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))

The output is 1, 1, 4, 2, 1, 1, 0, 0, exactly what the linear version produces. The 71 on day three waits two days for the 72, and the 76 on day six never sees anything warmer.

The mechanism is the inner loop breaking at the first warmer day. The initial value of zero is what handles the case where the loop finishes without finding one, since the answer for a day with no warmer future day is zero.

The trade-off to name is the quadratic worst case. A strictly increasing series makes every inner loop stop immediately, but a strictly decreasing series makes every inner loop run to the end, so the work is quadratic. The stack version avoids this by not looking forward at all: it only ever compares each day with the days it is currently blocking. Writing the naive version first is still worthwhile in an interview, because it forces you to be precise about what the answer means, in particular whether equal temperatures count and what happens when no warmer day exists.