[Solution]Problem 81: Daily Temperatures [Microsoft]
Monotonic Stack
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
Talked about the spring; had a winter storm,
God Bless Rochester. What’s the weather like in your part of the world? I’d be curious to know.
This question can be found as Leetcode 739. Daily Temperatures.
Problem
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]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
You can test your solution here
Step 1: Setting up the Solution
As always, a good first step is to read through the problem to figure out the skeleton of the solution. Upon reading, a few things stand out to us-
Firstly, we can see a simple case that’s handed to us on a silver platter. Peep the text- If there is no future day for which this is possible, keep answer[i] == 0 instead. This gives us a rather straightforward line of code to start with-
res = [0] * len(temperatures)
We can initialize our code with this right off the bat. This isn’t the greatest contribution to the solution, but it helps us reduce the scope just a teensy bit. And that’s how we eat our elephant- one bite at a time.
Step 2: Small Test Cases
We have a question, and we understand what to do. We need to know how to do it. This is where our ol’ buddy- sample test cases- comes in. We use the small test cases to hopefully figure out a bigger pattern that will lead to our solution.
How do we utilize the right test cases? We utilize the techniques covered in the post on case-by-case analysis to impact the kinds of input our solution will run into. Based on this, we can utilize 3 kinds of test cases-
Arrays where the digits are sorted in ascending order - such as [1,2,3,4]
Arrays sorted in descending order - [4,3,2,1]
Mixed up Arrays - [1,4,3,22,19]
When our string is Type-1, we end up with [1,1,…,0]. Similarly when we have our string being Type-2, our final is [0,0,0…,0]. This leads to an interesting observation- the last day will always have 0 (since there are no warmer days after it). It’s not particularly earth-shattering, but vocalizing it is a good way to secure some brownie points.
Time to tackle the final type of input- the mixed type. This is clearly the hardest part. But take a second to consider this- what makes it so hard? That can give us some insight into the problem.
Step 3: Tackling the Transitions
Looking at Type 3 and comparing it to the other two, one thing is clearly different- the difference in transitions. Unlike the other two types of input, the subarrays of this kind of an array will switch between being in ascending and descending orders. Consequently, if we could keep track of when our sub-array transitions from ascending to descending (or vice-versa), we would be able to solve the problem.
This is the one insight that is key to threading this solution. Most tech blogs/videos covering this question/similar questions just say that they will use the Monotonic Stack to solve the question. At best, they will work through some flimsy examples. Unfortunately, this won’t help people who haven’t come across many Mono-Stack Questions. If you’ve ever been confused about why certain questions use monotonic stacks now you have your answer.
A monotonic stack is useful when we need to maintain a monotonic ordering of elements in a stack (either increasing or decreasing) and efficiently process the elements in a specific order. It can be used in a variety of problems that involve finding the next or previous element that satisfies a certain condition.
-A general rule of thumb.
Step 4- Using the Mono-Stack
In our case, the use of the monotonic stack should become clear. We want to use it to find the next day that is warmer than the current one. Once we hit that warmer day, we know that the day we are currently at is the warmest in the subarray we are considering. So we want to update our stack accordingly. This is accomplished through the following computation-
stack = [] #stores[temp, index]. Store both since they're relevant
if stack[-1][0] < temp: # i is the current index. temp is the temp at i
stackT, stackI = stack.pop()
res[stackI] = (i-stackI) Obviously, we will need to go through every temperature index to build our monotonic stack and do the computation for every value. That will be handled by the loop-
for i, temp in enumerate(temperatures):
while stack and stack[-1][0] < temp:
stackT, stackI = stack.pop()
res[stackI] = (i-stackI)
stack.append((temp, i))Time to put our code together.
Step 5: Putting it together
Our final solution looks like this-
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = [] #stores[temp, index]
for i, temp in enumerate(temperatures):
while stack and stack[-1][0] < temp:
stackT, stackI = stack.pop()
res[stackI] = (i-stackI)
stack.append((temp, i))
return resTime Complexity- O(n)
Space Complexity- O(n)
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Small Snippets about Tech, AI and Machine Learning over here
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd