Daily Temperatures (LeetCode 739)

The problem

You get an array temps of daily temperatures. For each day i, return how many days you must wait until a strictly warmer day. If no warmer day ever comes, the answer for that day is 0.

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

Day 2 (75) waits until day 6 (76), which is 4 days later. The last two days never see anything warmer than themselves.

How to think about it

Start with brute force. For each day, scan forward until you find a warmer day. That is O(n²): a long run of falling temperatures followed by one hot day makes every day scan almost to the end. With n up to 100,000 that is far too slow.

Flip the question. Instead of each day looking forward for its answer, let each new day resolve the earlier days it beats. When a warm day arrives, it is the answer for every earlier, colder day that is still unanswered.

The key insight: unanswered days form a decreasing sequence. Suppose days j < k are both unanswered and temps[j] < temps[k]. Then k would have answered j when it arrived. So the waiting days, read left to right, have decreasing temperatures, and the coldest is always the most recent. That means a stack of indices: a new day pops from the top while the top is colder, writing i - j for each popped j, then pushes itself.

Which pattern is this? Monotonic stack, “next greater element”. The tell is “for each element, how far to the next bigger one”. Store indices, not values, because the answer is a distance.

Approach

1. Create res = [0] * n and an empty stack st of indices.
2. For each index i with temperature t:
   • While st is non-empty and temps[st[-1]] < t, pop j and set res[j] = i - j.
   • Push i.
3. Indices left on the stack never found a warmer day, so they keep 0.
4. Return res.

Solution

def daily_temperatures(temps):
    res = [0]*len(temps); st = []          # st holds indices, temps decreasing
    for i, t in enumerate(temps):
        while st and temps[st[-1]] < t:    # today is warmer than day j
            j = st.pop(); res[j] = i - j
        st.append(i)
    return res
# daily_temperatures([73,74,75,71,69,72,76,73]) -> [1,1,4,2,1,1,0,0]

Dry run

Days 6 and 7 stay on the stack, so they keep 0. The answer is [1, 1, 4, 2, 1, 1, 0, 0].

Complexity

• Time: O(n). Each index is pushed once and popped at most once, so all the while-loop iterations together add up to at most n.
• Space: O(n). A strictly falling input keeps every index on the stack.

Edge cases and pitfalls

• Equal temperatures are not warmer. Use <, not <=, in the pop condition, or a day equal to an earlier one would wrongly “answer” it.
• Strictly decreasing input gives all zeros; strictly increasing gives all ones except a final 0.
• Storing values instead of indices loses the position you need for i - j.
• Single day returns [0].
• An alternative scans right to left and jumps using already-computed answers. It is also O(n) and O(1) extra space, but the stack version is easier to explain.

Related problems

• Next Greater Element I (LeetCode 496): the same stack, returning the value rather than the distance.
• Next Greater Element II (LeetCode 503): the same idea on a circular array.
• Online Stock Span (LeetCode 901): looks backward instead, counting how many previous days were not higher.