Daily Temperatures - Monotonic Stack - Leetcode 739 - Python
Вставка
- Опубліковано 1 чер 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/daily-te...
0:00 - Read the problem
1:51 - Drawing Explanation
9:25 - Coding Explanation
leetcode 739
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#monotonic #stack #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Наука та технологія
A small optimization - you need not store the (key, index) pair. You can just store the index in the queue. For each comparison just reference the array with the index in the queue. Got a faster compute and lesser space.
Great tip
Thanks
Kyu(queue)
for anyone wondering how the code will look like with this modification (imagine a "sliding window" technique of comparing index l and index r):
answer = [0] * len(temperatures)
stack = []
for r in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[r]:
l = stack.pop()
answer[l] = r-l
stack.append(r)
return answer
The first time hearing monotonic stack. The solution provided in leetcode with space complexity O(1) is even more amazing!!! This problem to me is too hard. I was only able to find brute force solution before watching this video and see leetcode solutions tab.
dw man.. the more you don't know and the more you look it up when you don't know, the more patterns you'll recognise later
Got TLE exception with the n^2 solution, thanks for this approach
I found this one really hard, i was only able to find a brute force solution. Thank you for the clean explanation. ^_^
Your coding tutorial helped me so much. Thank you.
This is so hard not beginner at all, there must be way easier problems covering the basics and more beginner friendly than this, no way someone solved this way, without solving similar problems like this before.
I THINK this is a mis-speak here at 10:17, you say "first thing we're going to do is see is our stack empty, and if it is ... " I believe you meant to say "if it's NOT empty, and if it's not ..." (meaning there is indeed something inside the stack).
To be clear -
```while stack and t > stack[-1][0]:``` - This while loop runs as long as stack is not empty and the current temperature t is greater than the temperature at the top of the stack (stack[-1][0]).
Hope this helps someone who was just as confused as I was about why we would be able to get the temperature and index out of an empty stack 😂
(This is not to criticize the world's greatest human on the planet for helping us lowly juniors get a handle on leetcode, it's just to help clarify for anyone who may have been confused).
I am currently doing you roadmap. My god, thank you so so so much for that. I am so grateful for that. It truly has helped grinding leetcode fun.
Clean explaination!
Love your videos! Thanks for the efforts!
Agreed
This was the first problem following Neetcode Roadmap that I was able to do by myself since I started studying two weeks back. Thanks for these videos!
Another way is to traverse from right to left in an array and start building a stack, that way for every position we should be able to find next warmer temperature on top of the stack
Can you please share the code for this approach, I was trying to build a solution in a similar manner but couldn't really come to a conclusion. Thanks!
@@anantprakashsingh8777 leetcode pr discussion mein hai
@@anantprakashsingh8777 I too tried this approach and here's how my solution looks like:
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
vector res(n, 0);
stack st;
st.push(make_pair(temperatures[n-1], n-1));
for(int i=n-2; i>=0;i--){
while(!st.empty() && st.top().first
best explainer of leetcode problems on the internet
Made so clear! Thank you.
great visual explanation!!
Great Explanation as always
Thank you
Thanks for neet explanation 😊 Also I think we can solve it iterating from end as well
How did you solve it by iterating from the end?
Great explanation as always. Thank you .
amazing explanation dude, thank you
Wow 😲 ... Brilliant solution!
How do I get from Brute force approach to this (or such) optimized solution?
Thanks man, liked and commented for support
Thanks! Great explanation!
Thankyou for helping us.
Beautiful videos.
Brilliant AF !!!!!!!!
O(n)?
Shouldn't we take in consideration the while loop? In worst case, might take long.
thank you mr. neet
Thanks! I did solve it but my mind jumped straight to DP (Like LIS) but it was pretty inefficient.
Same bro ... In fact I have seen a pattern that the problems involving monotonic stack or monotonic queue often make us think it's about dp !
Same. My head was stuck in dp until I saw the topics then I oh it's a stack problem. I mean there's some kind of memoization with monotonic stack
Fantastic!
Man this question is annoying its basically "if you know this you know it" aint no way I was gonna do it without this video
Thank you!!!
whats the tool you use for drawing the solutions?
Where does the variable stackT get used in the example code at 11:46 inside of the while loop?
It doesn't. There is no need to add a pair [temp, index] to the stack -- just index is enough.
there is a O(1) space soln there on leetcode
Good video.
This is extremely useful even though I code in c++.
Cpp coders want everyone to know they code in cpp. They’re like vegans 😅
Great solution explanation, although wouldn't this be more of an array problem? As I understand it you can only interact with the top of a stack, not the elements below it.
thank you sir
We can also get rid of the tuple and just store the indices (without the values) in the stack, since it's already exist in the temperatures array and we can use it...
Totally makes sense .
Assuming that I understand this correctly, I think that this might not work with duplicate temperatures (finding the index of a temperature value will only return its first occurence).
@@thermalmedia6454 No fetching from array using the index you can get the exact element.
👏 Yeap, just what I was thinking. Then use the original array to get the temp at that index
@@thermalmedia6454 No, we will get the temperature at the index we initially encountered it. Supposed you added index of 1 to the stack, when we get it from the stack either via peek() or pop(), and retrieve it from initial array temperatures[1], it will give us the temperature at that exact index.
I came up with this same O(n) solution, submitted it to Leetcode and got a Time Limit Exceeded error.
Looked at my code for ten minutes, trying to figure out how I could possibly optimize it. Then I tried running the long input that broke my code, and it ran pretty fast so I thought "something is weird here", and just submitted the answer again. Got "faster than 86%"... Turns out my answer was fine the whole time, it was just lag or something on the first submission.
I do appreciate Leetcode's problem set and how relevant it is to real interviews, but god I just hate how terribly inaccurate its speed testing is.
same here, I was slightly confused
Same, I get time exceeded like 75% o the time with the same solution
same here
Same here, I was like what the fu*k??. How to optimize this when its already O(N)
Thanks
What are like characteristics of a problem where monotonic stack is suitable?
I haven’t solved a lot of problem using mono stack, and having hard time knowing when to use it…
hey what is the run time you didnt tell in the video, and i dont know how to calculate it here because it is not like realy we pass time the array....
Runtime is O(n) - you simply iterate over the list of 'n' temperatures. Each iteration you push an element onto a stack O(1), and do some number of pops from the stack. Since we push 'n' elements, even though each step we can pop a variable amount of elements, the total number of these pops can't exceed 'n', so on average it's a single pop per iteration.
In the loop:
Pop stack and assign - O(1) average
Push stack - O(1)
Loop: O(n)
Overall: O(n)
Memory is also O(n) since worst case we would have a stack containing 'n' elements. We would run into this case if our temperatures were continually decreasing. 10,9,8,7,6,5,4,3,2,1 at the end of the iterations, our stack would contain every element ('n' elements), and our array to return would be all 0 since the condition of increasing was never met.
Nice 👍🏻
Hey, how are you, I don’t know you though, but I like your efforts buddy 👍🏻😊
Could you cover #2104 sum of subarray ranges? Thanks :)
Can someone explain to me why it's O(n) time complexity. Because we have one loop to iterate through all elements in the temperatures, and another loop on the stack? So my interpretation would be O(n^2) time in the worst case scenario. For example, if we have temperatures = [50, 49, 48, 47, 46, 45], then the stack = [[50, 0], [49, 1], [48, 2], [47, 3], [46, 4], [45, 5]]
Another version of next greater element problem!!!
I think there are not many people who can solve this problem in the first time without knowing about Monotonic Stack. Too hard.
But this algorithm is so cool, worth to learn
I agree bro had no clue how to do it - at first I tried brute force but when I saw this video I was like "no way I was gonna think of this"
Good job! and well done. I think the time complexity is still quadratic. Consider this example temperatures = [90, 80, 70, 60, 50, 40, 30, 100]
it is not quadratic bcoz in your example we are traversing 2N times not N*N times(i too got confused about this)
Thanks@@BhanuPrakash-if2wl As long as there is an inner while loop inside an outer for loop, the worst. case time complexity is quadratic. It will only be 2 * N, if you exited the first for loop, before starting the second while loop.
Having an inner loop does not mean quadratic, that's a common mistake people make. You have to look at the context, the inner loop will never run more than N times total, so it can't be quadratic.
@@NeetCode Then what exactly is the time and space complexity?
@@shreshtashetty2985
Time complexity is O(N) because each element can only be added to the stack once, which means the stack is limited to N pops. Every iteration of the while loop uses 1 pop, which means the while loop will not iterate more than N times in total, across all iterations of the for loop.
This gives a time complexity of O(2N) =O(N).
@NeetCode can you do 629. K Inverse Pairs Array? Im stuck for this question for the whole day? Please help me. 😭
its a fucking hard question i just left it.
@@CEOofTheHood @NeetCode help us
I cannot know how can this be O(n). For only increasing and only equal input temp it is O(n).
However, when there are increasing and decreasing temps in the array it it not O(n).
You can try putting a count variable inside both the loops and see.
10:17 I think you meant if our stack is not empty
i tried this with function...but it will run only for small number of arrays
Better approach:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
"""
Always try to find the next greater so easier to start from right hand side
"""
stack = []
n = len(temperatures)
result = [0] * n
for i in range(n-1, -1, -1):
#while the existing temperature is greater keep popping until you find the greater temperature in top of the stack
while stack and temperatures[stack[-1]]
I actually solved this using the sliding window but ended up failing test cases because it was too slow :| Using a monotonic stack is way easier.
To me at first glance it looked like to find the next greater element on right for each element
same here. I used two pointers in my first attempt
understood
Hey guys, here is my solution.. easier to understand I would hope:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = []
for i in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
res[j] = i - j
stack.append(i)
return res
How is this not O(n^2) ?, there is still an inner while loop whose length is 'n'?
actually it's O(n * 2), so O(n)
instead of keeping holes in the output array, i created the monotonic stack traversing backwards. LOL. Stupid things stacks make you do
There is the 47th test case in LeetCode - where N = 10^5 and temperatures = [99,99,99,99,99...N-1, 100]. With this approach it exceeds time limit
In worst case scenario the size of the stack will be 10^5 as n can be at the much. One alternate ways is to create a temp array of size 101 (as temperature cannot be more then 100) and when ever u want to find look at temp array starting from temperature [i+1] to 101. Time complexity is 0(100*n) but space will always remain constant more precise 0(100)
here the java code : class Solution {
public int[] dailyTemperatures(int[] temp) {
ArrayDeque stack = new ArrayDeque();
int ans[] = new int[temp.length];
// we need a strictly decreasing queue
for(int i=0; i
here we are using while loop inside for loop, so how come the time time-complexity is linear?
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
tempidx = {}
for i, n in enumerate(temperatures):
tempidx[n] = i
stack = []
res = [0] * len(temperatures)
for i in range(len(temperatures)):
while stack and stack[-1] < temperatures[i]:
val = stack.pop()
idx = tempidx[val]
res[idx] = i - idx
stack.append(temperatures[i])
return res
why this is wrong in some cases
There is an issue with the way the index of the value is calculated when updating the result (res) array.
The index variable should be updated to the current index i instead of the index of the popped value from the stack.
Here is the corrected code:
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
tempidx = {}
for i, n in enumerate(temperatures):
tempidx[n] = i
stack = []
res = [0] * len(temperatures)
for i in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return res
```python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
tempidx = {}
for i, n in enumerate(temperatures):
tempidx[n] = i
```
- The `Solution` class contains a method called `dailyTemperatures` that takes a list of temperatures as input and returns a list of integers.
- The `tempidx` dictionary is initialized to store the index of each temperature in the `temperatures` list.
- The `enumerate` function is used to iterate over the `temperatures` list, providing both the index `i` and the temperature `n` at each iteration.
- The index `i` of each temperature `n` is stored in the `tempidx` dictionary with the temperature as the key.
```python
stack = []
res = [0] * len(temperatures)
```
- An empty stack `stack` is initialized to keep track of the indices of temperatures.
- The `res` list is initialized with zeros, having the same length as the `temperatures` list. It will store the number of days to wait for a warmer temperature.
```python
for i in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
```
- The code iterates over the indices of the `temperatures` list using a `for` loop.
- Inside the loop, a `while` loop is used to check if the stack is not empty and the temperature at the top of the stack (index `stack[-1]`) is less than the current temperature `temperatures[i]`.
- If the condition is true, it means a warmer temperature is found. The index `idx` at the top of the stack is popped, and the corresponding value in the `res` list at index `idx` is updated with the difference between the current index `i` and `idx`, representing the number of days to wait for a warmer temperature.
- After the `while` loop, the current index `i` is appended to the stack.
```python
return res
```
- Finally, the method returns the `res` list, which contains the number of days to wait for a warmer temperature for each corresponding temperature in the input list.
The code uses a stack to keep track of the indices of temperatures and efficiently finds the next warmer temperature for each temperature in the list. The time complexity of this solution is O(n), where n is the length of the `temperatures` list, as each temperature is pushed and popped from the stack at most once.
U a God
Isn't it close to n^2 complexity in the worst case?
Took me a while to see it, but once we do it's easy - not a fan of these trick questions where it's easy only if we solved it before.
To me the solution is a stack that tracks the smallest value. If we come across a larger value, we keep popping from the stack. This works because values that work for larger values will also work for the smallest values on the top of stack.
wow i used to think that you explain things nicely but damn this is confusing. no offence
Excuse me sir but 69 is always greater. Sorry, I can’t help myself.
incase anyone is having difficulty understanding this. I found this video easier to understand.
ua-cam.com/video/ekFs9Nb2RNQ/v-deo.html
8:09 You talk about popping the stack but are still using the popped values to be present to indicate distance (for the number 75 in your example). Popping doesn't allow for that as it shortens arrays, so this explanation doesn't make much sense.
Also popping occurs from the end, shifting occurs from the beginning, and you're referring to "popping" numbers with earlier index values (inserted earlier) with items inserted later at the end, which also doesn't make sense at face value (you're placing the number in your stack in your explanation and then discussing popping earlier values).
**EDIT** This only makes sense when you get to the code section and realize you're storing the index in the value. It makes no sense (as I commented above) to a first-time observer watching your drawn explanation.
why you speak so fast
slow down mate