Teaching to learn: Daily Temperatures
This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.
Daily Temperatures is categorized as a medium difficulty. I would agree with this. I was able to solve for the naive solution relatively easily but a more efficient solution was not as obvious. Let’s take a look at which solutions I was able to understand.
This challenge can be found here.
Understanding the problem
We are given an array of sequential daily Temperatures, T, that have a temperature range between 30 and 100.
For each daily temperature in T we are asked to find the number of days until the next warmer day (looking forward into the future only).
We will be returning an array of days in between the current temperature and the next warmer day.
For example:
if we have an array T = [30, 31, 46, 68, 55, 74]
then our output would be days = [1,1,1,2,1,0]
If you looks at index 3 in T (T[3]= 68) you’ll notice the next day is not warmer (T[4] = 55). But they day after that is (T[5] = 74). If we subtract the indices of these two, the higher temp from the lower temp, then we get 5–3=2. Two is our answer so we have to place it in the days array at the correct index corresponding to the lower temp day (3). So we could say days[3] = 2. Check the output above and you will see this is correct.
One thing I noticed right off the bat is that the last item in our return array will always be 0 since there are no warmer temperatures that follow it. This may or may not be useful, but it’s nice to be aware of.
Let’s look at what the naive approach’s steps are.
Pseudo-code:
- Initialize an empty array to store # of days until a warmer temp: let days
- Loop over input T, for each temperature, compare to index + 1 in input T
- Search for first value larger than the current temperature
- Store the difference of their indices in the days array
- When finished looping, return the days array
The code:
I was able to submit this solution and have it accepted but the runtime was around 700ms. The time complexity is O(n²) since we are using a nested for loop to check each temperature against every other temperature in the same array that comes after the current temperature. That is pretty bad. I think we can do better!
Another Solution:
This problem lends itself to utilizing a stack since we are passing over data that can be processed later on as we encounter different temperatures.
As we go through the array T we can add the index of each temperature to a stack and check that stack on each iteration. We can check if the current temperature we are looking at is greater than the temps in the stack which are looking for a future-warmer-day.
If our current temp is higher than a temp in the stack, then we pop it off the stack and add the difference of our current index minus the popped value (the index of a previous temp).
Pseudo-code:
- Initialize an empty array for # of days that is the length of input T, filled with 0's
- Initialize an empty stack array which will hold indices of each temp in T
- Loop over input T length
- While stack is not empty and current temp is greater than top element in the stack (T[stacklength-1]) repeat step 5.
- Pop from the stack, set days[index-popped] = i -index-popped
- Outside while loop, push current index to the stack
- Once for loop completes, return days array
The code:
The most important part of this function is the while loop conditions. We only want to pop from the stack when there are values in the stack and when the current temperature is greater than the value on top of our stack.
This insures that all of our temps-with-warmer-future-days will be changed from a 0 to the correct number of days between the next warmer day in our days array.
This algorithm has a much better time complexity at O(n) with the same space complexity as the previous solution: O(n).
If you have another solution for this challenge or any pointers for me, let me know. Thanks!
