Problem Statement in English

You’re given a list of integers representing the temperatures on consecutive days.

For each day, you want to know how many days you would have to wait until a warmer temperature. If there is no future day with a warmer temperature, you should set it to 0 instead.

Approach

We can solve this problem using a stack. It also uses the concept of a monotonic decreasing stack.

Simply put, elements in the stack will always be smaller than the element at the top.

While the stack top is smaller than the current element, we pop the stack top and update the answer list, and then once the current element is smaller than the stack top, we push the current element to the stack.

In this case, since we may see the same temperature multiple times, we store the indices in the stack instead of the temperatures. That way we can update the answer list with the correct number of days to wait, by checking the index at the stack top, and the index we’re currently processing from the temperatures list.

Solution in Python


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # store the length of `temperatures`
        l = len(temperatures)

        # initialize the answer list
        ans = [0] * l

        # initialize the stack
        stack = []

        # iterate over the temperatures
        for i in range(l):
            # if the stack is not empty,
            # and the current temperature
            # is greater than the temperature indicated by the index
            # at the top of the stack
            while stack and temperatures[stack[-1]] < temperatures[i]:
                # pop the index from the stack
                index = stack.pop()

                # update the answer list
                ans[index] = i - index

            # append the current index to the stack
            # as we haven't found a warmer temperature for it yet
            stack.append(i)

        # return the answer list
        return ans

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements in the temperatures list.

  • Space: $O(n)$
    Since we use a stack to store the indices of the temperatures.

And we are done.