Last time we looked at 3Sum, which was solved using two pointers. This time we look at Daily Temperatures.

Problem statement

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

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Naive/Brute force solution

The naive solution is to use two nested loops to look through all the temperatures after the current temperature to find the first greater temperature, and then update the result array. This is a O(n^2) solution, which is not great. It's very basic so I'm not doing to code it here. We will do something better.

Better solution

What you have to notice while manually walking through this problem, is that if you have constantly increasing temperatures, it's really easy to find the next warmer day since it's just the next day. If however the next day isn't the warmest day, you have to keep looking until you find a warmer day then your initial day. What you'll notice here is that when you do eventually find a warmer day, you can update all the days before this warmer day to be the difference between the warmer day and the current day.

Essentially, you can use a stack to store all the days which are you haven't found a warmer day for. Then, when you find a day which is warmer than the top of your stack, you can remove that day from the stack and update it in the results array.

An example

The explanation is easier to understand with an example. I noticed this while just manually writing out a solution for the example input. I'll walk through it here.

Input: temperatures = [73,74,75,71,69,72,76,73]

We start with an empty stack and initialise a results array with zeros, since the question tells us to do that. We will go through the input array from left to right.

We start with 73. Since the stack is empty, we add it to the stack along with it's index, so that we can later update it in the results array.

We then look at 74 and compare it with the top of the stack. Since it's warmer, we pop the stack, update the results array by comparing the current index with the index of the top of the stack, and then add the current temperature to the stack.

We then do the same with 75.

Then 71 and 69 are also added to the stack, since neither are warmer than the previous top of the stack.

We then look at 72. This is warmer than 69, so we pop 69 from the stack, update the results array. We then check the top of the stack again, which is 71. So 72 is still warmer, so we pop the stack and update the results array again. We then finally add 72 to the stack.

You then continue this process until you reach the end of the input array. It doesn't matter if the stack is empty or not.

Code

From this explanation and walkthrough, it's quite trivial to code. If you want more similar problems, look into Monotonic Stack problems. This just means it's a stack where the values are always increasing or decreasing (such as with the temperatures).

def dailyTemperatures(temps: List[int]) -> List[int]:
    s = []
    res = [0] * len(temps)

    for i, n in enumerate(temps):
        # using s[-1] is kinda ugly, but it's fine for this problem
        while s and s[-1][0] < n:
            res[s[-1][1]] = i - s[-1][1]
            s.pop()
        s.append((n, i))
        
    return res

A note on time and space complexity

You might see a loop within a loop and be tempted to say this is O(n^2). This could be because you are looping through all the temperatures in the input and then looping through the stack which could reach up to size n is the temperatures are always decreasing. However, if this is the case, then we never go into the loop or pop from the stack since we never find a warmer day. So the worst case is actually O(n) time (and O(n) space).

You might then think, what if all the temperatures were decreasing, but then the last temperature was the warmest. Then we would have to loop through the entire stack. This is true, but we would only have to do this once. So the worst case is still O(n) time. Basically you can think of the worst case as O(2n) time. We never have to loop the inner loop n times for all n temperatures.

We can also slightly improve the space usage by only storing the index rather than the temperature and the index, but I like to store both 😊

References

• Daily Temperatures on LeetCode