As I practice more algorithm problems, I sometimes find it challenging to identify the right time to use the appropriate data structure. While, doing lots of problems is a sure bet to develop this perception, I have found that it is also important to have a thorough understanding of what is going on under the hood. I realized this, while making my last blog post. My last post was about trees, queues, and BFS. This one will be about stacks.
The Problem
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
How to Solve
Basically, we need to iterate through the list of temperatures. If T[i] < T[i+1] we can enter a 1 in our result array. Otherwise, we need to check T[i+2], T[i+3], … etc against T[i] until we find a value that is greater than T[i]. The appropriate value would then be entered into the result array. It should also be noted that the last value in the result array will always be 0. The last temperature in T has no proceeding temperatures to compare to.
I will be honest. I was not able to solve this problem optimally. My original brute-force solution used a nested for loop to check every temperature against every other temperature. Using nested for loops is not ideal and it resulted in a Big-O of O(n²).
When I looked at solutions submitted by other people, I saw lots of people using stacks to achieve a time complexity of O(n). Being a beginner to all this algorithm stuff, it took me a while to understand how the stack was being used. I think I understand it now. Here is a post on stacks if you need a refresher.
Instead of having to compare each temperature to ever other temperature, a stack will allow us to “archive” index values for the temperature array if a warmer temperature has not been found yet. We can then continue to iterate through the temperature array and if we find a warmer temperature, we simply subtract the “archived stack index” from the index of the warmer temperature.
Hopefully this high-level description will make more sense as we look at the code and then some illustrations of the algorithm in action.
The Code
Let’s take a look at the code to solve this problem. Read through the code and make as much sense of it as possible. Then we can go through it step-by-step and make sure that we understand it completely.
Here are the steps that the algorithm takes:
- Create an array that is the same length as the temperature array.
- Create an Integer stack.
- The for loop iterates for the length of the temperature array.
- There is a while loop that runs for every iteration of the for loop. The while loop will continue to run as long the stack isn’t empty and if the temperature that corresponds to the top value of the stack (which is an archived index value) is less than the current temperature value that the for loop is on.
- If those two conditions just mentioned are true then the top value is popped from the stack and a new value is added to the result array.
- If one of the conditions is false then the index for the current iteration of the for loop will get pushed onto the stack and the for loop will iterate to its next value.
Some Illustrations
I know what might be helpful! How about we use some illustrations to help us better understand what is going on in the algorithm.
Take a look at Figure A. It corresponds to when i = 0 in the for loop. The stack is empty, so 0 gets pushed onto the stack. i = 0 changes to i = 1.
In Figure B, our stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 0 is popped from the stack. The stack then becomes empty which breaks the while loop. 1 is pushed onto the stack. i = 1 changes to i = 2.
In Figure C, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 1 is popped from the stack. The stack then becomes empty which breaks the while loop. 2 is pushed onto the stack. i = 2 changes to i = 3.
In Figure D, the stack is not empty, but the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. The while loop doesn’t run. 3 gets pushed onto the stack. i = 3 changes to i = 4.
Figure E is quite similar to what just happened in Figure D. The stack is not empty, but the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. The while loop doesn’t run. 4 gets pushed onto the stack. i = 4 changes to i = 5.
In Figure F, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 4 is popped from the stack. The stack is not yet empty though, so the while loop will continue to run. i = 5 will remain the same as the while loop runs again.
In Figure G, the while loop continues with another iteration and i = 5 still. The temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop.
Here is where it gets interesting. Up until now only values of 1 have been added to result. Now, 5 – 3 = 2 is being added to result. This is where the stack comes in handy. If the i + 1 of a temperature is not greater than it, then a stack allows us to store the index until we find a temperature that is greater. Then the difference between the two indexes can be added to result.
Ok, let’s get back to Figure G. A value of 2 is added to result and 3 is popped from the stack.
The temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. 5 gets pushed to the stack. i = 5 changes to i = 6.
In Figure I, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 5 is popped from the stack. 2 is now at the top of the stack.
In Figure J, the while loop runs again while i = 6. The temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 2 is popped from the stack. The stack is empty, breaking the while loop. 6 is then pushed onto the stack. i = 6 changes to i = 7.
In Figure K, the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. 7 is pushed onto the stack. i = 7 changes to . . .
That’s it! i = 7 is the last index of the temperature array. When an array is initiated it has all zeros by default, so the last two values in the result array will be 0, which is what they should be. As mentioned before, the last value of the result array will always be 0. The temperature at i = 6, which is 76 has no proceeding warmer temperatures, so it gets a 0 as well.
Output:
result: [1, 1, 4, 2, 1, 1, 0, 0]
Time Complexity
As mentioned earlier the time complexity for this algorithm is O(n) with n being the number of elements in the temperature array.
Space Complexity
The space complexity is O(n) as well. The result array will be the same length as the temperature array. Also, the height of the stack will never exceed the length of the temperature array.
If you want some more Big-O tips and tricks then I know of a great place to start.
Get Better at Algorithms!
Algorithms and data structures are pretty tough. They are definitely taking a while for me to get the hang of them. However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me. If I missed any that have been helpful to you, be sure to mention them in the comments.
- Cracking the Coding Interview – Great resource. Really gets you in the right mindset for interviews. You can find it here.
- Elements of Programming Interviews – Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
- Grokking the Coding Interview – Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
- Back To Back SWE – Great YouTube Channel. Highly recommend.
- Kevin Naughton Jr. – Another awesome YouTube channel. Great at going over problems and gives helpful advice.
- Base CS – Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
- Coding Challenge Website – There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
- Pramp – Do mock interviews! The sooner the better! Pramp has been a huge help to me.
Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!
