Daily Temperatures

Learning goal: Translate the next-warmer-day question into an efficient array process.

Core idea For each day, we want the distance to the first later temperature that is strictly warmer. A direct scan from every day may revisit the same future days many times, creating quadratic work. Instead, we will postpone unresolved days and let a future warmer temperature resolve them in one pass.

Algorithm plan

• Create an answer array filled with 0.
• Process temperatures from left to right.
• Keep unresolved day indices in a decreasing-temperature stack.
• When a warmer temperature arrives, resolve colder indices at the top.

Micro-example For [73, 74], index 0 waits for index 1, so answer[0] = 1 - 0 = 1. The final index has no later day, so its answer remains 0.

Pitfalls

• The answer is a day gap, not the warmer temperature itself.
• Equal temperatures are not warmer; use a strict comparison.
• Store indices so the gap can be computed.

Recap

• Unresolved days wait in a stack.
• Every answer is a future index minus the current index.
• Default 0 handles days with no warmer future.

Learning goal: Understand why a decreasing stack identifies exactly the days a warmer temperature can resolve.

Core idea The stack contains indices whose warmer day has not appeared yet. Their temperatures decrease from bottom to top, so the top is the most recent and easiest day to resolve. When the current temperature is warmer than the top, that top day has found its first warmer future day; continue popping while the current temperature resolves more colder days.

Data structure model

Micro-example After processing 73, 74, 75, the stack is empty because each new temperature resolves the previous one. After 71, 69, the stack holds indices [2,3,4] with temperatures [75,71,69].

Pitfalls

• Do not pop when the current value is equal; equality preserves the decreasing invariant.
• Push the current index after resolving older days.
• The stack may contain days that will ultimately receive 0.

Recap

• The stack is decreasing by temperature.
• Popping means an answer has been found.
• One warmer day can resolve several colder days in sequence.

Learning goal: Implement the one-pass monotonic-stack algorithm without losing the nearest-warmer guarantee.

Core idea Process each temperature once. Before pushing index i, repeatedly pop indices whose temperatures are lower than temperatures[i]; because indices are processed from left to right, i is the first warmer day encountered for every index popped now. Any indices left on the stack are at least as warm as the current day and remain unresolved.

Algorithm plan

answer = [0] * n
stack = []
for i from 0 to n - 1:
    while stack is not empty and temperatures[i] > temperatures[stack.top]:
        old = stack.pop()
        answer[old] = i - old
    stack.push(i)
return answer

Micro-example At index 5, temperature 72 pops index 4 (69) and records 1, then stops at index 3 (71) only after recording 2. The remaining stack still decreases: 75, 72.

Pitfalls

• Compare temperatures through stack indices, not stack positions.
• Assign the answer before discarding the popped index.
• Push every index, including the final one.

Recap

• Resolve with a while loop, then push.
• The stack stores indices, while temperatures enforce monotonicity.
• The result is ready after one left-to-right pass.

Learning goal: Distinguish the monotonic-stack solution from tempting but inefficient alternatives.

Core idea The most common mistake is scanning forward independently for every day. That approach is easy to write, but a long decreasing or repeating input causes many days to inspect the same future values, producing O(n^2) time. The monotonic stack shares that work: a future warmer day resolves all eligible waiting indices as it pops them.

Algorithm plan

• Use a strict comparison: pop while temperatures[i] > temperatures[stack[-1]].
• Keep answer initialized to zeros.
• Leave remaining stack indices untouched at the end.
• Test increasing, decreasing, equal, and one-element inputs.

Micro-example For [80,79,78], no value is warmer, so the stack ends with all indices and the answer is [0,0,0]. For [70,70], equality does not count as warmer, so the answer is also [0,0].

Pitfalls

• Treating equal temperatures as warmer creates incorrect gaps.
• Forgetting that a decreasing suffix legitimately stays in the stack.
• Assuming every index must be popped; the final stack represents zeros.

Recap

• Avoid a forward scan nested inside the main loop.
• Strictly warmer means >.
• Zeros naturally cover no-solution and trailing cases.

Learning goal: Justify the linear runtime and recognize when this pattern applies.

Core idea Although one iteration may pop many indices, each index can be pushed only once and popped only once. Across the entire run, the total number of stack operations is at most 2n, so the algorithm is linear rather than quadratic. The stack can hold every index in a decreasing input, requiring linear auxiliary space.

Algorithm plan

• Scan the array once from left to right.
• Charge one push and at most one pop to each index.
• Store the answer array and the monotonic stack.
• Return the completed gaps after the scan.

Micro-example For eight temperatures, there are eight pushes and at most eight pops. In the walkthrough, indices 0,1,3,4,2,5 are popped once, while 6,7 remain and correctly keep zero.

Pitfalls

• Do not call the nested while loop quadratic without an amortized analysis.
• Separate output space from auxiliary stack space when discussing memory.
• The pattern applies to “next greater” or “next warmer” questions, not arbitrary future searches.

Recap

• Time: O(n) because every index is pushed and popped at most once.
• Auxiliary space: O(n) for the stack; output also uses O(n).
• The monotonic stack turns repeated future scans into one shared process.