Problem Description

You are given an array temperatures where each element represents the daily temperature. For each day, you need to find how many days you would have to wait to get a warmer temperature.

Specifically, for each position i in the array, you need to find the smallest number of days you'd have to wait after day i to get a temperature that is strictly warmer than temperatures[i]. If there's no future day with a warmer temperature, the answer for that position should be 0.

For example, if temperatures = [73, 74, 75, 71, 69, 72, 76, 73]:

• For day 0 (temperature 73), the next warmer day is day 1 (temperature 74), so you wait 1 day
• For day 1 (temperature 74), the next warmer day is day 2 (temperature 75), so you wait 1 day
• For day 2 (temperature 75), the next warmer day is day 6 (temperature 76), so you wait 4 days
• For day 3 (temperature 71), the next warmer day is day 5 (temperature 72), so you wait 2 days
• And so on...

The result would be [1, 1, 4, 2, 1, 1, 0, 0].

The task is to return an array where each element represents the number of days to wait for a warmer temperature, or 0 if no warmer day exists in the future.

Intuition

The key insight is that we need to find the next greater element for each position in the array. When we think about this problem, we realize that as we traverse the array, we need to keep track of elements that are still "waiting" for a warmer day.

Consider traversing from right to left. At any position i, we want to know which future days (to the right) could potentially be the answer. However, not all future days matter - if day j has temperature 75 and day k (where k > j) has temperature 73, then day k will never be the answer for any day before j because day j is both closer and warmer.

This observation leads us to maintain only the "relevant" future days - those that form an increasing temperature sequence when viewed from right to left. This is where the monotonic stack comes in.

By traversing from right to left and maintaining a stack of indices where temperatures are monotonically increasing (from stack top to bottom), we can efficiently find the next warmer day:

• When we're at position i, we pop all indices from the stack whose temperatures are less than or equal to temperatures[i] (they're not useful anymore)
• The remaining top of the stack (if it exists) is the closest day with a warmer temperature
• We then add the current index i to the stack for future positions to consider

The stack essentially filters out all the irrelevant days and keeps only those that could potentially be answers for elements we haven't processed yet. This reduces our search space and gives us an efficient O(n) solution since each element is pushed and popped at most once.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

We implement the solution using a monotonic stack that traverses the array from right to left. The stack maintains indices of temperatures in monotonically increasing order (from top to bottom).

Here's the step-by-step implementation:

1. Initialize data structures:

   • Create an empty stack stk to store indices
   • Create a result array ans of the same length as temperatures, initialized with zeros
   • Get the length n of the temperatures array

2. Traverse from right to left (i from n-1 to 0):

   For each position i:

   a. Clean the stack: While the stack is not empty and the temperature at the top index is less than or equal to temperatures[i], pop elements from the stack. This removes all days that are not warmer than the current day.

   while stk and temperatures[stk[-1]] <= temperatures[i]:
       stk.pop()

   b. Find the answer: After cleaning, if the stack is not empty, the top element represents the nearest warmer day. Calculate the number of days to wait as stk[-1] - i.

   if stk:
       ans[i] = stk[-1] - i

   c. Add current index: Push the current index i onto the stack for future iterations to consider.

   stk.append(i)

3. Return the result: After processing all elements, return the ans array.

The algorithm maintains the invariant that the stack contains indices in increasing order of their temperatures. This ensures that for any position, we can quickly find the next warmer day by looking at the stack top after removing all cooler or equal temperature days.

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once. Space Complexity: O(n) - In the worst case (decreasing temperatures), the stack could contain all indices.

Example Walkthrough

Let's walk through a small example with temperatures = [72, 71, 75, 73, 70].

We'll traverse from right to left (index 4 to 0), maintaining a stack of indices.

Initial state:

• stk = [] (empty stack)
• ans = [0, 0, 0, 0, 0] (result array initialized with zeros)

Step 1: i = 4 (temperature = 70)

• Stack is empty, so no warmer day exists
• ans[4] = 0 (remains 0)
• Push index 4 to stack: stk = [4]
• Current state: ans = [0, 0, 0, 0, 0]

Step 2: i = 3 (temperature = 73)

• Check stack top: temperatures[4] = 70 <= 73, so pop index 4
• Stack becomes empty after popping
• No warmer day exists, ans[3] = 0
• Push index 3 to stack: stk = [3]
• Current state: ans = [0, 0, 0, 0, 0]

Step 3: i = 2 (temperature = 75)

• Check stack top: temperatures[3] = 73 <= 75, so pop index 3
• Stack becomes empty after popping
• No warmer day exists, ans[2] = 0
• Push index 2 to stack: stk = [2]
• Current state: ans = [0, 0, 0, 0, 0]

Step 4: i = 1 (temperature = 71)

• Check stack top: temperatures[2] = 75 > 71, so don't pop
• Stack has index 2, so next warmer day exists
• ans[1] = 2 - 1 = 1 (wait 1 day)
• Push index 1 to stack: stk = [2, 1]
• Current state: ans = [0, 1, 0, 0, 0]

Step 5: i = 0 (temperature = 72)

• Check stack top: temperatures[1] = 71 <= 72, so pop index 1
• New stack top: temperatures[2] = 75 > 72, so don't pop
• Stack has index 2, so next warmer day exists
• ans[0] = 2 - 0 = 2 (wait 2 days)
• Push index 0 to stack: stk = [2, 0]
• Final state: ans = [2, 1, 0, 0, 0]

Final Result: [2, 1, 0, 0, 0]

This means:

• Day 0 (72°): wait 2 days for 75°
• Day 1 (71°): wait 1 day for 75°
• Day 2 (75°): no warmer day
• Day 3 (73°): no warmer day
• Day 4 (70°): no warmer day

The monotonic stack efficiently maintains only the relevant indices, allowing us to find the next warmer day in constant time for each position.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the temperatures array once from right to left. Although there's a nested while loop inside the for loop, each element is pushed onto the stack exactly once and popped at most once. This means that across the entire execution, the total number of operations for stack push and pop combined is at most 2n. Therefore, the amortized time complexity is O(n), where n is the length of the temperatures array.

Space Complexity: O(n)

The algorithm uses two additional data structures:

• The stack stk which in the worst case (when temperatures are in increasing order) can store all n indices
• The answer array ans which has exactly n elements

Both contribute to a space complexity of O(n), where n is the length of the temperatures array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Comparison Operator

One of the most common mistakes is using the wrong comparison operator when popping from the stack.

Incorrect Implementation:

# Wrong: using < instead of <=
while stack and temperatures[stack[-1]] < temperatures[i]:
    stack.pop()

Why it's wrong: This would keep equal temperatures in the stack, but we need strictly warmer temperatures. If we keep equal temperatures, we might incorrectly identify a day with the same temperature as a "warmer" day.

Correct Implementation:

# Correct: using <= to remove equal temperatures too
while stack and temperatures[stack[-1]] <= temperatures[i]:
    stack.pop()

2. Storing Values Instead of Indices

Another frequent error is pushing temperature values onto the stack instead of indices.

Incorrect Implementation:

stack = []
for i in range(n - 1, -1, -1):
    while stack and stack[-1] <= temperatures[i]:  # Wrong: comparing value with value
        stack.pop()
  
    if stack:
        result[i] = ???  # Can't calculate days difference without indices!
  
    stack.append(temperatures[i])  # Wrong: pushing value instead of index

Why it's wrong: We need indices to calculate the number of days between two positions. If we only store values, we lose positional information.

Correct Implementation:

stack = []
for i in range(n - 1, -1, -1):
    while stack and temperatures[stack[-1]] <= temperatures[i]:  # Compare values using indices
        stack.pop()
  
    if stack:
        result[i] = stack[-1] - i  # Calculate days using indices
  
    stack.append(i)  # Push index, not value

3. Wrong Traversal Direction with Incorrect Logic

Some might try traversing left-to-right but apply right-to-left logic, or vice versa.

Incorrect Implementation (mixing traversal directions):

# Traversing left to right but using right-to-left logic
for i in range(n):  # Left to right
    while stack and temperatures[stack[-1]] <= temperatures[i]:
        stack.pop()
  
    if stack:
        result[i] = stack[-1] - i  # This would give negative values!
  
    stack.append(i)

Correct Alternative (Left-to-Right Approach):

stack = []
result = [0] * n

for i in range(n):
    # Pop and update result for all indices waiting for current temperature
    while stack and temperatures[stack[-1]] < temperatures[i]:
        idx = stack.pop()
        result[idx] = i - idx  # Update the popped index's result
  
    stack.append(i)

return result

In this left-to-right approach, we update the result when we find a warmer day, not when we process the original day. The logic is fundamentally different from the right-to-left approach.