LeetCode 739: Daily Temperatures

First off, let’s start with the problem statement.

Daily Temperatures - LeetCode

You may also find the problem statement above.

In short, we are given an array of temperatures and we are required to output a result array filled with indices that indicate the smallest number of days we have to wait to come across a higher temperature for the current temperature.

Namely, temperature[i] is the “i th” day temperature we currently have, and result[i] is the number of days to wait to come across a higher temperature than the “i th” day temperature.

There are a number of ways to solve this, I will explain the “decreasing stack” methodology since I come across this problem when I was doing Leetcode stack exploration card.

Let’s take a look at the example input and output.

For an array of [30, 40, 50, 60], the output is [1,1,1,0].

It is pretty straightforward since this array is monotonically increasing, we can actually also find a pattern that, result[i]= (higher temperature’s index) — i, where i is the index of current temperature encountered.

So for result[0] here, it equals 1–0 = 1 since temperature[1] is higher than temperature[0].

Then the next question is, how do we update each index to get the final answer?

We can probably use a Stack structure that only records the index of temperature that hasn’t find a higher temperature.

For instance, we can place 1 in the stack initially when we didn’t find 50 in the example. Once we iterate to 50, we can check the stack’s top element to get the last index of the array that didn’t find a higher temperature and compare.

If the current temperature > temperature[stack[-1]), then we found a temperature that is larger than temperature[stack[-1]) and we can go ahead and pop the stack[-1] off and update the corresponding index’s number of days need to wait. Remember, the stack keeps track of the indices only, so we derive the result[stack. pop()] = i — idx

Since the last element, we iterate to doesn’t find a larger temperature yet (if it exists), we add “i the index” to the stack and wait for the next iteration to update it.

Hence, when we assemble the code, it actually looks like this [in Python]:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        #initialize the stack
        stack = []
        stack.append(0)
        #initialize the result, it has the same length as temperature array as well.
        n = len(temperatures)
        result = [0] * n
        
        
        # We choose to iterate from 1 to n since 0th element won't be greater than 0th
        for i in range(1,n):
            
            # Check if the current temperature       
#is larger than the stack
            # top's index's corresponding temperature
            if temperatures[i] > temperatures[stack[-1]]:
                # If so, we iteratively pop the indices off until we found a 
                # index that is larger than current temperature.
                while stack and temperatures[i] > temperatures[stack[-1]]:
                    idx = stack.pop()
                    result[idx] = i - idx
                    
            # Add current temperatures' index to stack since we haven't iterate 
            # to a larger temperature yet. 
            stack.append(i)
            
        return result

I just started writing explanations on Leetcode solutions, there are definitely a lot of areas that I could improve and any feedbacks are appreciated. If you think I am doing a good job explaining these solutions, please consider following me, which really motivates me to continue writing these articles.

Cheers and happy coding!

My code submission for better code readability:

https://leetcode.com/submissions/detail/551772327/