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.
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
@@randomystick can you explain what he did with stackInd? it makes no sense to me. how is he indexing in his list with a variable that has no value but was initialized?
@@trevor6711 since he used an array to store temp/index, he was able to extract the index, which is array[1], from the temp, which is array[0]. If he did X = stack.pop(), X would be equal to [array[0], array[1]] Since he did X, Y = stack.pop(), X = array[0] and Y = array[1]
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.
I followed the advice of find a brute force solution first and then see if you can improve it. The brute force approach was relatively easy to find, but then... blank. I figured it'd had something to do with a stack, but dang.
Got the solution quickly, took me an hour to implement. beats 30% runtime and 80% memory. But remember when solving this problem, we know in advance it has to do with Stacks, so use that as a hint.
I was able to solve this one pretty quickly as I had done the NeetCode Minimum Stack question before which had stumped me. The code is pretty different but it felt like the same concept of tracking mins/max in one direction
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.
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 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--){
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).
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!
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
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...
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, 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.
if you wonder if its O(n) or O(n^2) time, read this: its still O(n) even in worst scenario if we have [4,3,2,1], our stack would be [4,3,2,1], however, when we at 3, we know 3 < 4, so we don't have to loop through the whole stack, we simply append it, thats O(1), same for all the other operations, we simply return the res with everything as 0, even if we have something like [4,3,2,1,5], we only process [4,3,2,1] once when we reach 5 (bigger than all of them). thats only O(n), so maximumly, we process each node twice and thats it, imagine we have [4,3,2,1,3], when we reach the last 3, we process only the [2,1,] from [4,3,2,1], then we stop, our stack would look like [4,3], the algorithm is done
One other possible solution instead of storing the temperature, index pair in the stack is to just store the indices directly and then do the comparisons in the while loop through indexing
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]]
actually its still O(n) even in worst scenario if we have [4,3,2,1], our stack would be [4,3,2,1], however, when we at 3, we know 3 < 4, so we don't have to loop through the whole stack, we simply append it, thats O(1), same for all the other operations, we simply return the res with everything as 0, even if we have something like [4,3,2,1,5], we only process [4,3,2,1] once when we reach 5 (bigger than all of them). thats only O(n), so maximumly, we process each node twice and thats it, imagine we have [4,3,2,1,3], when we reach the last 3, we process only the [2,1,] from [4,3,2,1], then we stop, our stack would look like [4,3], the algorithm is done
How is the space complexity of the DP approach constant? Shouldn't it be linear too since we are using a vector to return the final result. The only optimization is on the space we save by eliminating the use of a stack. So stack solution is O(2n) (which is basically O(n)) and DP solution is O(n).
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.
This question is more like a sliding window problem. However, the left pointer is not a "single" pointer, but a group of left pointers. After the sliding window condition is triggered, all left pointers are compared with the right pointer. it's genius. while [left1, left2, left3, left4] < right: instead of while left < right:
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.
@@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).
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 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.
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 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
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
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.
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)
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.
The drawing might be misleading, you are putting the comparison value into the stack in your drawing where it is not yet in the stack while you are comparing them. You only put that comparison value into the stack after each time you have finished comparing everything which is after each while loop.
i just dont understand how you can pop in the middle of the stack, like 69 is not on top of the stack, how can you pop it off? isnt stack LIFO? so you have to pop 72 before you can pop 69 right?
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.
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.
Tbh the "it's intuitive to use the stack here" is not right. To me it felt like you jumped to it without reason. Seeing the solutino i can see that it works, but it's taking a while to get an intuitive understanding why it works.
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.
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
@@randomystick can you explain what he did with stackInd? it makes no sense to me. how is he indexing in his list with a variable that has no value but was initialized?
@@trevor6711 since he used an array to store temp/index, he was able to extract the index, which is array[1], from the temp, which is array[0].
If he did X = stack.pop(), X would be equal to [array[0], array[1]]
Since he did X, Y = stack.pop(), X = array[0] and Y = array[1]
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
I followed the advice of find a brute force solution first and then see if you can improve it. The brute force approach was relatively easy to find, but then... blank. I figured it'd had something to do with a stack, but dang.
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
I was able to come up with the sub-optimal min-heap solution, but wouldn't have come up with this.
which is a lot of leetcode questions
Got the solution quickly, took me an hour to implement. beats 30% runtime and 80% memory. But remember when solving this problem, we know in advance it has to do with Stacks, so use that as a hint.
@@omarllama that's mediocre , you're mediocre .
I was able to solve this one pretty quickly as I had done the NeetCode Minimum Stack question before which had stumped me. The code is pretty different but it felt like the same concept of tracking mins/max in one direction
Got TLE exception with the n^2 solution, thanks for this approach
Same here but optimized to 0(100n), worked but wasn't optimal
I found this one really hard, i was only able to find a brute force solution. Thank you for the clean explanation. ^_^
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.
Using two pointers you can get O(1) space complexity
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
@@anantprakashsingh8777
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Deque stack = new ArrayDeque();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
res[i] = 0;
} else {
res[i] = stack.peek() - i;
}
stack.push(i);
}
return res;
}
i like this way more its like we know what future element will be before processing past ones
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).
Right!
noticed this too in his explanation, threw me off as well
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!
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.
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"
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.
if you wonder if its O(n) or O(n^2) time, read this: its still O(n) even in worst scenario if we have [4,3,2,1], our stack would be [4,3,2,1], however, when we at 3, we know 3 < 4, so we don't have to loop through the whole stack, we simply append it, thats O(1), same for all the other operations, we simply return the res with everything as 0, even if we have something like [4,3,2,1,5], we only process [4,3,2,1] once when we reach 5 (bigger than all of them). thats only O(n), so maximumly, we process each node twice and thats it, imagine we have [4,3,2,1,3], when we reach the last 3, we process only the [2,1,] from [4,3,2,1], then we stop, our stack would look like [4,3], the algorithm is done
Your coding tutorial helped me so much. 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?
One other possible solution instead of storing the temperature, index pair in the stack is to just store the indices directly and then do the comparisons in the while loop through indexing
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
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]]
actually its still O(n) even in worst scenario if we have [4,3,2,1], our stack would be [4,3,2,1], however, when we at 3, we know 3 < 4, so we don't have to loop through the whole stack, we simply append it, thats O(1), same for all the other operations, we simply return the res with everything as 0, even if we have something like [4,3,2,1,5], we only process [4,3,2,1] once when we reach 5 (bigger than all of them). thats only O(n), so maximumly, we process each node twice and thats it, imagine we have [4,3,2,1,3], when we reach the last 3, we process only the [2,1,] from [4,3,2,1], then we stop, our stack would look like [4,3], the algorithm is done
there is a O(1) space soln there on leetcode
Clean explaination!
How is the space complexity of the DP approach constant? Shouldn't it be linear too since we are using a vector to return the final result. The only optimization is on the space we save by eliminating the use of a stack. So stack solution is O(2n) (which is basically O(n)) and DP solution is O(n).
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.
best explainer of leetcode problems on the internet
Love your videos! Thanks for the efforts!
Agreed
This question is more like a sliding window problem. However, the left pointer is not a "single" pointer, but a group of left pointers. After the sliding window condition is triggered, all left pointers are compared with the right pointer. it's genius.
while [left1, left2, left3, left4] < right:
instead of
while left < right:
How do I get from Brute force approach to this (or such) optimized solution?
This is extremely useful even though I code in c++.
Cpp coders want everyone to know they code in cpp. They’re like vegans 😅
Made so clear! Thank you.
Great explanation as always. Thank you .
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).
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 was stumped on this one, and the solution is always so painfully obvious when I finally give up on a problem, lol
Thanks! Great explanation!
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)
Wow 😲 ... Brilliant solution!
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
Great Explanation as always
Thank you
Thanks man, liked and commented for support
@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
thank you mr. neet
great visual explanation!!
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…
amazing explanation dude, thank you
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
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
Thankyou for helping us.
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.
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.
Beautiful videos.
O(n)?
Shouldn't we take in consideration the while loop? In worst case, might take long.
nope still O(n)
nice explanation
10:17 I think you meant if our stack is not empty
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)
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.
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.
The drawing might be misleading, you are putting the comparison value into the stack in your drawing where it is not yet in the stack while you are comparing them. You only put that comparison value into the stack after each time you have finished comparing everything which is after each while loop.
Thank you!!!
i just dont understand how you can pop in the middle of the stack, like 69 is not on top of the stack, how can you pop it off? isnt stack LIFO? so you have to pop 72 before you can pop 69 right?
i am so dumb, forgot that pairs exist
that was the light buld moment, stack st;
😭😭😭😭😭😭😭😭😭😭😭😭
it can be solved without pairs
Brilliant AF !!!!!!!!
whats the tool you use for drawing the solutions?
Could you cover #2104 sum of subarray ranges? Thanks :)
thank you sir
Guys this video seems outdated, his websites solution page shows more optimised DP solution without extra space.
Fantastic!
Thanks
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.
Good video.
Another version of next greater element problem!!!
instead of keeping holes in the output array, i created the monotonic stack traversing backwards. LOL. Stupid things stacks make you do
i tried this with function...but it will run only for small number of arrays
Nice 👍🏻
Hey, how are you, I don’t know you though, but I like your efforts buddy 👍🏻😊
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)
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.
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
understood
Even after the concept, i found it hard to code. Phew.
here we are using while loop inside for loop, so how come the time time-complexity is linear?
Tbh the "it's intuitive to use the stack here" is not right. To me it felt like you jumped to it without reason. Seeing the solutino i can see that it works, but it's taking a while to get an intuitive understanding why it works.
U a God
Excuse me sir but 69 is always greater. Sorry, I can’t help myself.
wow i used to think that you explain things nicely but damn this is confusing. no offence
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.
incase anyone is having difficulty understanding this. I found this video easier to understand.
ruclips.net/video/ekFs9Nb2RNQ/видео.html
😘
honestly i do not understand this at all
why you speak so fast
slow down mate