Monotonic Stacks and Queues

As described in the Introduction, we can use a stack as an auxiliary data structure to solve problems and improve overall time complexity.

Let's use Daily Temperatures as our example.

A brute force approach would consist of checking every possible temperature:

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * len(temperatures)

        for i in range(n):
            for j in range(i + 1, n):
                t1 = temperatures[i]
                t2 = temperatures[j]
                if t1 < t2:
                    res[i] = j - i
                    break

        return res

Which has the following complexity:

• Time: $O(n^2)$
• Space: $O(n)$

Where $n$ is the size of the temperatures list.

Can we do better? Of course, yes.

Suppose to have an increasing sequence like [1, 2, 3, 4, 5]. The result would be [1, 1, 1, 1, 0]. In fact, the i-th temperature is always less compared to the i+1 one, except for the last one, which has no higher value.

Another example could be [1, 1, 1, 1, 100]. The corresponding result would be [4, 3, 2, 1, 0]. This example suggests that the last value is the target value for all.

So we could start from the last position and keep a monotonic increasing stack to keep track of the temperatures. In this way, the stack will contain a list of possible candidates for our target temperature.

For example, for [100, 30, 40, 50, 60, 200] we can notice that once we process the first element, the stack is:

30
40
50
60
200

In fact, since we iterate backward, we will process the first element in the last iteration. At this point, we can pop from the stack until we find a higher temperature.

Lastly, to calculate the actual distance, we also need to store the index of the i-th temperature. So, the previous stack would look something like:

(30, 1)
(40, 2)
(50, 3)
(60, 4)
(200, 5)

The optimal solution is:

from typing import List, Tuple


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * len(temperatures)
        stack: List[Tuple[int, int]] = []

        for i in range(n - 1, -1, -1):
            temperature = temperatures[i]

            while stack and stack[-1][0] <= temperature:
                stack.pop()

            if stack:
                res[i] = stack[-1][1] - i

            stack.append((temperature, i))

        return res

Which has the following complexity:

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the temperatures list.