Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Examples

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation: 
- Day 0: temperature 73, wait 1 day for warmer (74)
- Day 1: temperature 74, wait 1 day for warmer (75)
- Day 2: temperature 75, wait 4 days for warmer (76)
- Day 3: temperature 71, wait 2 days for warmer (72)
- Day 4: temperature 69, wait 1 day for warmer (72)
- Day 5: temperature 72, wait 1 day for warmer (76)
- Day 6: temperature 76, no warmer day (0)
- Day 7: temperature 73, no warmer day (0)

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Explanation: Each day has a warmer day the next day.

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]
Explanation: Day 0 waits 1 day, day 1 waits 1 day, day 2 has no warmer day.

Constraints

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

Thinking Process

  1. Monotonic Stack Pattern: Classic pattern for “next greater element” problems - conceptually elegant
    • Better cache locality: sequential array access vs random stack operations
    • No stack overhead: avoids push/pop function calls
    • Direct memory access: simpler access patterns for CPU
  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).
Stack top push / pop LIFO — monotonic stack scans array

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Monotonic stack (this problem) O(n) O(n) Next greater/smaller element
Parentheses matching O(n) O(n) Push open, pop on close
Expression evaluation O(n) O(n) Operand + operator stacks
Stack simulation O(n) O(n) Process in LIFO order

Solution

Note: While this solution is conceptually elegant and easier to understand, Solution 2 is faster in practice due to better cache locality and avoiding stack overhead.

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        rtn = [0] * n
        s = []
        
        for i in range(n):
            while s and temperatures[i] > temperatures[s[-1]]:
                prev = s.pop()
                rtn[prev] = i - prev
            
            s.append(i)
        
        return rtn

Solution Explanation

Approach: Monotonic stack (this problem)

Key idea: 1. Monotonic Stack Pattern: Classic pattern for “next greater element” problems - conceptually elegant

How the code works:

  1. Monotonic Stack Pattern: Classic pattern for “next greater element” problems - conceptually elegant
    • Better cache locality: sequential array access vs random stack operations
    • No stack overhead: avoids push/pop function calls
    • Direct memory access: simpler access patterns for CPU
    • Stack matches nested or LIFO structure (parentheses, monotonic scans).
    • Push on open / larger; pop when the current element resolves pending work.

Walkthrough — input temperatures = [73,74,75,71,69,72,76,73], expected output [1,1,4,2,1,1,0,0]:

  • Day 0: temperature 73, wait 1 day for warmer (74)
  • Day 1: temperature 74, wait 1 day for warmer (75)
  • Day 2: temperature 75, wait 4 days for warmer (76)
  • Day 3: temperature 71, wait 2 days for warmer (72)
  • Day 4: temperature 69, wait 1 day for warmer (72)
  • Day 5: temperature 72, wait 1 day for warmer (76)
  • Day 6: temperature 76, no warmer day (0)
  • Day 7: temperature 73, no warmer day (0)

Solution 1: Monotonic Stack

  • Time Complexity: O(n)
    • Each index is pushed onto the stack exactly once
    • Each index is popped from the stack at most once
    • Overall: O(n)
  • Space Complexity: O(n)
    • Stack can contain at most n indices in worst case
    • Result array: O(n)
    • Total: O(n)

Solution 2: Right-to-Left with DP Jumping

  • Time Complexity: O(n)
    • Each index is visited once
    • Jumping forward skips already-processed days using DP information
    • Worst case: O(n) when temperatures are in decreasing order
    • In practice, faster than Solution 1 due to better cache locality and no stack operations
    • Overall: O(n)
  • Space Complexity: O(1) excluding output array
    • Only uses a few variables
    • Result array: O(n) required by problem
    • Total: O(1) extra space (vs O(n) for stack in Solution 1)

      Common Mistakes

  1. All increasing: [30,40,50,60] → [1,1,1,0]
  2. All decreasing: [60,50,40,30] → [0,0,0,0]
  3. Single element: [73] → [0]
  4. Same temperatures: [30,30,30] → [0,0,0]

  5. Mixed pattern: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

  6. Wrong comparison: Using >= instead of > (should be strictly greater)
  7. Index confusion: Mixing up indices when calculating wait days
  8. Stack order: Maintaining increasing instead of decreasing stack
  9. Not handling empty stack: Forgetting to check if stack is empty before popping
  10. Jump logic error: In Solution 2, not checking rtn[j] == 0 before jumping

Tags

Array, Stack, Monotonic Stack, Medium

Key Takeaways

  1. Monotonic Stack Pattern: Classic pattern for “next greater element” problems - conceptually elegant
  2. Decreasing Stack: Stack maintains indices in decreasing temperature order
  3. Efficient Resolution: When finding a warmer day, resolve all waiting colder days
  4. DP Jumping Approach: Right-to-left processing with jumping reuses computed information - faster in practice
  5. Why DP Jumping is Faster:
    • Better cache locality: sequential array access vs random stack operations
    • No stack overhead: avoids push/pop function calls
    • Direct memory access: simpler access patterns for CPU
    • O(1) extra space: more memory-efficient
  6. Single Pass: Both approaches achieve O(n) time with a single pass through the array

References

Template Reference