Daily Temperatures

Intuition

This question tests a concrete understanding of the Monotonic Stack concept.
The key insight here is to take the difference in their indices in the temperatures list
That is to say: we use the concept of the Monotonic Stack similar to Next Greater Element I, but we expand it to denote the following:
- If an element was on the stack, then it must be greater than any element that came after it.
  - This is because we pop elements which don’t satisfy this criterion.
- Therefore, when an element is popped off the stack, the first element greater than it is the current temperature, in which it is i - index of that temperature days prior to a greater temperature following that element.

Complexity

Runtime

$O (N)$ where N is the number of temperatures, since there are at most N elements on the stack processed, and at most N temperatures.

Space

$O (N)$ for stack holding elements.

Code

Monotonic Stack

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []
 
        for i in range(len(temperatures)):
            while stack and temperatures[i] > stack[-1][1]:
                idx, _ = stack.pop()
                res[idx] = i - idx
            stack.append((i, temperatures[i]))
 
        return res

INCORRECT Code Using Count to Keep Track

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = [(0, temperatures[0])]
 
        for i in range(1, len(temperatures)):
            count = 0
            while stack and temperatures[i] > stack[-1][1]:
                count += 1
                idx, val = stack.pop()
                res[idx] += count
            if stack:
                res[stack[-1][0]] += count
 
            stack.append((i, temperatures[i]))
        
        for idx, _ in stack:
            res[idx] = 0
        
        return res

I originally used “count” to keep track of the number of days, but this doesn’t work since we may pop off elements but not all from the stack (in the case where the current element is not greater than all on the stack), meaning we lose track of count on the next runthrough of the loop.

Notes

Cards

START Basic Front: Daily Temperatures Back: Use a Monotonic Stack with current index - index corresponding to value on stack = “number of days passed”

END

Devin's Blog

Explorer