Daily Temperatures

Signal

"For each element, find the next element to the right that's greater" is the monotonic-stack signature — any "next greater/smaller element" phrasing should trigger a decreasing (or increasing) stack of indices, not nested loops.

Approach

Keep a stack of indices whose answer isn't known yet, maintained so their temperatures are decreasing. For each new day, while the stack's top has a colder temperature than today, pop it — today is its answer, at distance current_index - popped_index. Then push today's index.

Skeleton

stack = []  # indices, temps decreasing
ans = [0] * n
for i, t in enumerate(temps):
    while stack and temps[stack.top] < t:
        j = stack.pop()
        ans[j] = i - j
    stack.push(i)

Solution

def daily_temperatures(temperatures: list[int]) -> list[int]:
    ans = [0] * len(temperatures)
    stack: list[int] = []  # indices, temperatures decreasing
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

Complexity

O(n) time — each index is pushed once and popped at most once, despite the nested-looking while loop. O(n) space for the stack and the answer array.

Pitfalls

• Storing temperatures on the stack instead of indices — you need the index to compute the distance i - j, not just the value.
• Using <= instead of < in the comparison would pop on ties, giving a wait of 0 days incorrectly treated as "found" for equal temperatures.
• Reaching for brute force (nested loop, O(n²)) is the natural first instinct; naming the monotonic stack explicitly is what turns this into O(n).