I think this is one of those problems that can be solved in an interview setting if, and only if you've solved it before. There's no way someone would be able to come up with this solution in an interview 😮💨
its also me for the first time touching the concept of mono stack. For those who's also struggling to interpret mono-stack thoroughly for the 1st time, I recommend just move on to BFS/DFS, DP, hard array problems etc. and come back to this once you are comfortable with those other skills. Then you'll notice the way you see mono-stack is much more clear and different, trust me:))
I came up with a solution by building a rectangle from each index, going left until you reach a smaller value and right until you reach a smaller value. The rectangle is the sum of those two, minus the current rectangle height (because you counted it twice, once going left and once going right). For an array where every value is the same, this is O(n^2), so it timed out! I think an interviewer would accept it anyway though.
Either you have lot's of experience with similar problems, or you already solved this one. Sometimes I have to accept that I am not a genious that comes up with solutions like this on the spot, let alone being a jr, but with enough time problems become repetitive and with that experience I might come up with that solution one day.
@@eloinpuga It comes with practice. You can't assume that just because a solution seems new to you now, that it's not a standard algorithm or approach.
@@B3TheBand Coming up with an O(n2) brute force solution is easy. Sorry but if you think the interviewer is not interested in finding the O(n) solution then you're kind of missing the point.
Dude's awesome as he always is! Just a suggestion, if we add a dummy [0] to the right of heights, the extra handling for right boundary can be avoided. I tried that and got accepted. :)
It's a pretty hard question. But NeetCode explained it in a pretty good way. At first, I couldn't understand it. But in the end, I found it a very good video.
I would've never come up with that good of a solution with my abilities right now. Leetcode has humbled me a lot since I am an almost straight A student in college. I trip up on mediums and hard easily, it shows that GPA doesn't mean anything and I still have a long way to go with my problem solving skills.
You do realize that leetcode is a completely different skill on its own right? College's alrotithms course is completely different from LC. Only some transferrable skill.
This was my first ever hard problem, and I was so close to solving it- I hadn't considered the fact that I could leave some stacks until the end to calculate them using [ h * (len(height)-i)], so I had that for loop nested inside the original one, which gave me some time limit issues. These videos explain things super well, thanks 👍
Good stuff. I came up with a solution that used a red black tree (TreeMap in Java), but the use of a monotonic stack is brilliant and much easier to reason with.
watched it twice, and the second time, it seems more clear that why and how the monotonic increasing stack came out to be the solution, and it's well explained, and its proven that it works too. thank you! definitely a really hard problem.
Got to 96/98 then got time limit exceeded. Now time to watch your approach :D. Wow, that approach was much better, was able to code it up no problem. Thanks again!!!
I solved the problem by myself and cameup with this intutive approach, just find next smaller and prev smaller element class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) nse = [n]*n pse = [-1]*n ans = 0 #nse stack = [0] for i in range(1,n): while stack and heights[i]
brother this is just the naive approach having a time complexity of O(4N),though great you solved it on your own appreciate it man cos i couldnt on my own
This is the last problem in the Grind 75. I solved it with O(n^2) but the time limit exceeded. You're gonna help me complete the Grind 75 let's goooooo
This is the best optimized solution I've seen till now..👌🏻👏🏻 Thank you so much for the best explanation.❤Your solutions are always optimal and also get to learn complete thought process step by step . I always watch solution from this channel first. This channel is amazing, I follow all the playlist of this channel. I feel fortunate that I got this channel when I started preparing DSA.
thanks, bud. stuck on this for hours trying to over engineer a solution using sorting + linked list but it kept failing because TLE. I like your approach so much better.
For anyone who wants a simpler solution to the example in the video, you can simply add another height to the input with `height.append(0)`: class Solution: def largestRectangleArea(self, heights: List[int]) -> int: stack = [] res = 0 heights.append(0) for i in range(len(heights)): j = i while stack != [] and stack[-1][1] > heights[i]: popped = stack.pop() j = popped[0] area = (i - j) * popped[1] res = max(area, res) stack.append((j, heights[i])) return res
Watched 3 times, now it really clicked! If two consecutive bars have the same height it will be hard to do expanding to left, but the first one will take care of the rectangle anyway.
Awesome video. This would be worth re-recording. 1 feedback is to visualize the stack in the opposite order where last in is at the top instead of the bottom. That would make it slightly easier to follow.
This algorithm is pretty intuitive from the point of view that, in order to calculate the effect of each additional vertical bar the information needed from existing bars is exactly the stack.
i spend over an hour on this problem and got this O(n^2) divide and conquer solution that finds the lowest height, updates maxarea based on a rectangle using that lowest height, and then splits the array into more subarrays deliminated by that lowest height and repeats. i thought i was so smart lol
Java Code: if (heights.length == 1) return heights[0]; int area = 0; Stack st = new Stack();
for (int i = 0; i < heights.length; i++) { int[] curr = new int[] {i, heights[i]}; while (!st.isEmpty() && st.peek()[1] > curr[1]) { int[] popped = st.pop(); // Calculate height of this block only area = Math.max((i-popped[0]) * popped[1], area); curr[0] = popped[0]; } st.push(curr); } int len = heights.length; while (!st.isEmpty()) { int[] curr = st.pop(); area = Math.max(area, (len-curr[0]) * curr[1]); }
A much better explanation and reasoning for this solution is this: We want to keep track of all rectangles we can create from left to right. How can we keep track of these rectangles? Well, if we iterate through the heights, we could add every rectangle to a list. Lets choose to store the index of the heights. But then this would be the same as our heights list except just indices (i.e. {0,1,2,3,4,5...}) and not give us any new information. So we need a way to remove elements in a way that allows us to retain knowledge of all rectangles we could create. What if we remove rectangles from our list when we know we reached their maximum limit? In other words, we know when a rectangle cant grow anymore which is when it meets another height that is lower (or when it meets the end of the heights i.e. an edge case), so whenever we meet a lower height lets remove the previous rectangle, calculate the largest area we could make with that rectangle, and finally update our max. But wait, what if we had a sequence of increasing heights that were all larger than the lower (i.e. {4,6,7,3}? They would all cant grow any further past the height 3. So we need to keep removing previous values too. Since we want to remove the sequence of last inputted heights, we should use a stack as the implementation for this list. We can keep removing/popping the last heights as long as they are larger than the height we just stopped at. Ok so at this point lets review. We have a list of heights: Heights = {1,4,2,4,6,7,3} We go through the list, add indices to our stack and remove them when we meet a lower height. Which means our stack should look like this {0,2,6} by the end of our passthrough. We end up popping the following indices {1,3,4,5} corresponding to the heights {4,4,6,7}. We can see easily how to calculate the area of these rectangles. Lets take the second height of 4. When we add it to the stack, we add its index of 3. When we start popping off values, we reached index 6 with height 3. By merely multiplying the height of 4 by the difference in our stopping index (6) and our start index of (3) we get the max area of that rectangle (i.e. 12). But now our final stack still has rectangles and they can keep going till the end of the list. Our stack is {0,2,6} corresponding to heights {1,2,3}. How do we calculate their area? If we visualize the heights, then intuitively we can see 1 can go throughout the list so we can merely take the list length and multiply it by 1. But for 2 and 3 we can't bc they cant extend throughout the list. They have different starting points. The height of 2 starts at index 1 and 3 starts at index 3. Both of these start when they meet a height lower than it. One way we can solve this is by merely iterating backwards through the heights from our indices until we find a height lower than each. This would be our stopping point. This would theoretically be amortized O(n) operation since a monotonically increasing heights list {1,2,3,4,5,6} would yield the worst possible final stack of {0,1,2,3,4,5} and we would only iterate once through the list of heights. Ill leave this as an exercise for you to reason through. Another way to answer that final question is the way NeetCode did it, which is quite intelligent and relies on you being able to answer one question: how can we utilize the prior work we did so we can know when each of these indices start their rectangles? This is a part of the reasoning process that you'll just have to hope you realize on an interview bc i dont believe this can be taught. To realize how to solve this problem, you simply need to keep doing these types of problems and reason it out yourself. So ill leave this part as an exercise for you, and you can use the video to see the answer.
I honestly got this entire solution except for the part where you extend the start index back to where it couldve started, couldnt find the efficient way to do it
Good Video: one suggestion , if we push -INT_MAX extra height to the input , we dont have to bother about elements remaining in stack after the iteration.
U a God. Never thought about saving the indexes into the stack and then calculating the width by len(heights) or the current index we are on. Very smart.
Can't we use Kadane's algorithm for this problem? I tried it with Kadane's algorithm and it passes most of the test cases except when the horizontal and vertical area are same. Here's my code: class Solution: def largestRectangleArea(self, heights: List[int]) -> int: if not heights: return 0 ans=float('-inf') heights=[0]+heights dim=[0,1] #dimension=[height,length] for i in range(1,len(heights)): temp1=[heights[i],1] #vertical area considering the current bar only temp2=[min(heights[i],dim[0]),dim[1]+1] #horizontal area dim=temp1 if temp1[0]*temp1[1]>=temp2[0]*temp2[1] else temp2 ans=max(dim[0]*dim[1],ans) return ans
Hey, love your videos. Was stuck on this problem and rewrote your solution in ruby and broke down each part to understand it. It failed on test [2,1,2] which was 87/98. Looking through the comments of this video I saw someone suggested appending 0 to heights to prevent traversing the stack and this solution actually can pass [2,1,2]. Video might require a small update, just informing you.
Playing the end at 0.5x while still trying to understand it and he's sounds drunk and saying " this is the most intuitive solution at least from my perspective " loll
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
I think this is one of those problems that can be solved in an interview setting if, and only if you've solved it before. There's no way someone would be able to come up with this solution in an interview 😮💨
Thanks! Your explaination helps a lot!
Even with the video, this problem is still hard for me to understand and solve. but, anyway, thanks for explaining
Samesies.
feel a little bit relieved seeing your comment :( it is so hard
its also me for the first time touching the concept of mono stack. For those who's also struggling to interpret mono-stack thoroughly for the 1st time, I recommend just move on to BFS/DFS, DP, hard array problems etc. and come back to this once you are comfortable with those other skills. Then you'll notice the way you see mono-stack is much more clear and different, trust me:))
It is hard. If they ask me this on an interview, I doubt I'll come up with this eficient solution 😅😅😅
Maybe with a lot of hints!
When I see the monotonic stack tag on leetcode my hope of solving the problem dissipates
Bumped into one of your earliest uploads and I am amazed at your progress. You improvements in tone is impressive!
this is awesome. I don't know how someone can come up with the solution in an interview for the first time.
I came up with a solution by building a rectangle from each index, going left until you reach a smaller value and right until you reach a smaller value. The rectangle is the sum of those two, minus the current rectangle height (because you counted it twice, once going left and once going right).
For an array where every value is the same, this is O(n^2), so it timed out! I think an interviewer would accept it anyway though.
Either you have lot's of experience with similar problems, or you already solved this one. Sometimes I have to accept that I am not a genious that comes up with solutions like this on the spot, let alone being a jr, but with enough time problems become repetitive and with that experience I might come up with that solution one day.
@@eloinpuga It comes with practice. You can't assume that just because a solution seems new to you now, that it's not a standard algorithm or approach.
@@B3TheBand Coming up with an O(n2) brute force solution is easy. Sorry but if you think the interviewer is not interested in finding the O(n) solution then you're kind of missing the point.
@@gorgolyt Cool. I'm a Software Engineer at Amazon. You?
Repetition really helps nail down the point into my head till it clicks. Liked and subscribed. Thank you!
Dude's awesome as he always is! Just a suggestion, if we add a dummy [0] to the right of heights, the extra handling for right boundary can be avoided. I tried that and got accepted. :)
This is done in Elements of Programming Interviews in Python book.
to be honest, I found solution in the video is more intuitive and easier to understand
What an intuitive way to handle the left boundary . Kudos!
sincerely the best explanation for lc questions in 21st century. thank you!
I agree with you
Nah lc explanations of the 17th century were bangers.
LeetCode was founded in 2011. 🙄
man you are underrated, such a clear explanation. keep it up my guy!
OG video, you can hear the keyboard clicks, the background noise, perfect just perfect, Thanks for the explanation
It's a pretty hard question. But NeetCode explained it in a pretty good way. At first, I couldn't understand it. But in the end, I found it a very good video.
I would've never come up with that good of a solution with my abilities right now. Leetcode has humbled me a lot since I am an almost straight A student in college. I trip up on mediums and hard easily, it shows that GPA doesn't mean anything and I still have a long way to go with my problem solving skills.
All the best! :)
You do realize that leetcode is a completely different skill on its own right? College's alrotithms course is completely different from LC. Only some transferrable skill.
This was my first ever hard problem, and I was so close to solving it-
I hadn't considered the fact that I could leave some stacks until the end to calculate them using [ h * (len(height)-i)], so I had that for loop nested inside the original one, which gave me some time limit issues.
These videos explain things super well, thanks 👍
I watched couple of videos, but this one does the job :)
The stack O(N) method deserves to be a hard problem. But you explained it so well, it did not feel that difficult after watching your video. thank you
Such a clever solution with minimal usage of extra space and minimal function calls. Love it.
Good stuff. I came up with a solution that used a red black tree (TreeMap in Java), but the use of a monotonic stack is brilliant and much easier to reason with.
how did you do that?
I like the intuition part to clear up why stack is being used, thanks!
This is the best explanation I found for this problem. Thank you
watched it twice, and the second time, it seems more clear that why and how the monotonic increasing stack came out to be the solution, and it's well explained, and its proven that it works too. thank you! definitely a really hard problem.
Thank you for the most clear explanation and code as always!
Blown away by the logic!
Thankyou for the clear and concise explanation.
Thanks!
Got to 96/98 then got time limit exceeded. Now time to watch your approach :D. Wow, that approach was much better, was able to code it up no problem. Thanks again!!!
I was able to come up with brute force and the test cases are like 87, can you please share your approach.
Man you are the best across UA-cam in this, by far!
you made it easy to understand but I dont think I could come up with that answer in an interview setting if I have never seen the problem before....
ultimate solution! no other explanation can beat this.
You could use the trick to iterate for(int i = 0; i
amazing algorithm and explanation. Really great solution you got.
I solved the problem by myself and cameup with this intutive approach, just find next smaller and prev smaller element
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
nse = [n]*n
pse = [-1]*n
ans = 0
#nse
stack = [0]
for i in range(1,n):
while stack and heights[i]
brother this is just the naive approach having a time complexity of O(4N),though great you solved it on your own appreciate it man cos i couldnt on my own
with every video the respect for you just increases. Great work navdeep!
first i didn't catch this solution but now i understand. You have topnotch skills.
Just awesome man, such a nice explanation! I needed only the first ten minutes to figure it out what I was missing
best explanator in youtube
This is the last problem in the Grind 75. I solved it with O(n^2) but the time limit exceeded. You're gonna help me complete the Grind 75 let's goooooo
This is the best optimized solution I've seen till now..👌🏻👏🏻 Thank you so much for the best explanation.❤Your solutions are always optimal and also get to learn complete thought process step by step . I always watch solution from this channel first. This channel is amazing, I follow all the playlist of this channel. I feel fortunate that I got this channel when I started preparing DSA.
Very clear explanation on the example!! Thank you very much!!👍
Your explanation is so good, I didn't even have to look at the code solution!
thanks, bud. stuck on this for hours trying to over engineer a solution using sorting + linked list but it kept failing because TLE. I like your approach so much better.
This was a hard problem for me and this video is the one which worked out best for me. Thanks for this video.
The explanation is so nice I am able to solve question just by listening approach. So simple
For anyone who wants a simpler solution to the example in the video, you can simply add another height to the input with `height.append(0)`:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
res = 0
heights.append(0)
for i in range(len(heights)):
j = i
while stack != [] and stack[-1][1] > heights[i]:
popped = stack.pop()
j = popped[0]
area = (i - j) * popped[1]
res = max(area, res)
stack.append((j, heights[i]))
return res
Watched 3 times, now it really clicked!
If two consecutive bars have the same height it will be hard to do expanding to left, but the first one will take care of the rectangle anyway.
Thank you. So easy to write code after explanation.
Elegant and effective solution, explanation helped me to understand what am I missing in my way of thinking, thank you! 👍
This is an excellent explanation! Thank you so much for these videos!
Thank you Neetcode, this was helpful!
very nice...Thanks for a detailed, clear explanation
Thank you so much for the video. You make hard questions easy
:)
Wow. This is so intuitive. Thanks man, you're helping me out a lot!!
Awesome explanation
Took me hours to get this one. Nice explanation NeetCode.
Awesome video. This would be worth re-recording. 1 feedback is to visualize the stack in the opposite order where last in is at the top instead of the bottom. That would make it slightly easier to follow.
Imagine if this is the coding interview problem that you need to solve under 1 hour for the job
This algorithm is pretty intuitive from the point of view that, in order to calculate the effect of each additional vertical bar the information needed from existing bars is exactly the stack.
beautiful drawing and great explanation!!!!!!
Thanks for a clear explanation!
I used recursion and partitioning by the min element. It worked but was too slow for large lists.
i spend over an hour on this problem and got this O(n^2) divide and conquer solution that finds the lowest height, updates maxarea based on a rectangle using that lowest height, and then splits the array into more subarrays deliminated by that lowest height and repeats. i thought i was so smart lol
i did the same thing but got a time limit exceeded error on leetcode. did your solution pass?
@@krishivgubba2861 nope haha that's why i had to come here to see the solution
Thank you so so much!! I finally understand how to solve it
I was so close to solving my first hard problem, One day i will become just as good as this guy
beautiful drawing and explanation❤❤
Thanks for the clear explanation.
The Best explanation but I needed the solution in java. Thank you anyways.
Thanks for the explanation with illustration!
अद्भुत, अकल्पनीय, अविश्वसनीय
jai shree ram
Thanks a lot buddy, you explanation was really good. 😘
Just Amazing algorithm and explanation...Thank a lot
Awesome explanation, finally understood it.
The best ever explaination ..💞
Great explanation.
Best explanation, helped a lot. Thanks a lot!!!
how do you come up with this in an interview. just knowing monotonic stack isn't enough, must be legit einstein's cousin
you cant do this in an interview unless you know the answer , or as you said you must have einsteins genes
Even SWEs usually get easy/medium leetcode questions. This is just for training. And I didn't understand the explanation.
A super hard problem...but good explanation, thx so much.
great explanation!
Java Code:
if (heights.length == 1) return heights[0];
int area = 0;
Stack st = new Stack();
for (int i = 0; i < heights.length; i++) {
int[] curr = new int[] {i, heights[i]};
while (!st.isEmpty() && st.peek()[1] > curr[1]) {
int[] popped = st.pop();
// Calculate height of this block only
area = Math.max((i-popped[0]) * popped[1], area);
curr[0] = popped[0];
}
st.push(curr);
}
int len = heights.length;
while (!st.isEmpty()) {
int[] curr = st.pop();
area = Math.max(area, (len-curr[0]) * curr[1]);
}
return area;
A much better explanation and reasoning for this solution is this:
We want to keep track of all rectangles we can create from left to right. How can we keep track of these rectangles? Well, if we iterate through the heights, we could add every rectangle to a list. Lets choose to store the index of the heights. But then this would be the same as our heights list except just indices (i.e. {0,1,2,3,4,5...}) and not give us any new information. So we need a way to remove elements in a way that allows us to retain knowledge of all rectangles we could create.
What if we remove rectangles from our list when we know we reached their maximum limit? In other words, we know when a rectangle cant grow anymore which is when it meets another height that is lower (or when it meets the end of the heights i.e. an edge case), so whenever we meet a lower height lets remove the previous rectangle, calculate the largest area we could make with that rectangle, and finally update our max.
But wait, what if we had a sequence of increasing heights that were all larger than the lower (i.e. {4,6,7,3}? They would all cant grow any further past the height 3. So we need to keep removing previous values too. Since we want to remove the sequence of last inputted heights, we should use a stack as the implementation for this list. We can keep removing/popping the last heights as long as they are larger than the height we just stopped at.
Ok so at this point lets review. We have a list of heights:
Heights = {1,4,2,4,6,7,3}
We go through the list, add indices to our stack and remove them when we meet a lower height. Which means our stack should look like this {0,2,6} by the end of our passthrough. We end up popping the following indices {1,3,4,5} corresponding to the heights {4,4,6,7}. We can see easily how to calculate the area of these rectangles. Lets take the second height of 4. When we add it to the stack, we add its index of 3. When we start popping off values, we reached index 6 with height 3. By merely multiplying the height of 4 by the difference in our stopping index (6) and our start index of (3) we get the max area of that rectangle (i.e. 12).
But now our final stack still has rectangles and they can keep going till the end of the list. Our stack is {0,2,6} corresponding to heights {1,2,3}. How do we calculate their area? If we visualize the heights, then intuitively we can see 1 can go throughout the list so we can merely take the list length and multiply it by 1. But for 2 and 3 we can't bc they cant extend throughout the list. They have different starting points. The height of 2 starts at index 1 and 3 starts at index 3. Both of these start when they meet a height lower than it. One way we can solve this is by merely iterating backwards through the heights from our indices until we find a height lower than each. This would be our stopping point. This would theoretically be amortized O(n) operation since a monotonically increasing heights list {1,2,3,4,5,6} would yield the worst possible final stack of {0,1,2,3,4,5} and we would only iterate once through the list of heights. Ill leave this as an exercise for you to reason through.
Another way to answer that final question is the way NeetCode did it, which is quite intelligent and relies on you being able to answer one question: how can we utilize the prior work we did so we can know when each of these indices start their rectangles? This is a part of the reasoning process that you'll just have to hope you realize on an interview bc i dont believe this can be taught. To realize how to solve this problem, you simply need to keep doing these types of problems and reason it out yourself. So ill leave this part as an exercise for you, and you can use the video to see the answer.
Not amortized o(n) in cases of duplicate heights however.
Thanks NeetCode!
Makes sense, but there's no way I woulda figured this out in an interview without having seen the problem before lol
Thank you for brilliant explanation
I get it every time I watch it and then I forget it after a few weeks, lmao
Imagine if your Kryptonite was a leetcode question. Well, ladies and gentlemen, I present to you....
I honestly got this entire solution except for the part where you extend the start index back to where it couldve started, couldnt find the efficient way to do it
I finally understood how to solve largest rectangle in histogram after watching this video
the monotonic stack is genius
I can't stop mySelf without commenting "No one can explain better than this"
Good Video: one suggestion , if we push -INT_MAX extra height to the input , we dont have to bother about elements remaining in stack after the iteration.
We don't necessarily have the option to add elements to the input, especially if it's a fixed size array (C / Java)
So well explained!
@NeetCode what keyboard & switch are you using? the clacky sound as you type is so satisfying. And thanks for the excellent content!
Thanks!! Super helpful!
U a God.
Never thought about saving the indexes into the stack and then calculating the width by len(heights) or the current index we are on. Very smart.
Amazing explanation！
Can't we use Kadane's algorithm for this problem? I tried it with Kadane's algorithm and it passes most of the test cases except when the horizontal and vertical area are same. Here's my code:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
if not heights:
return 0
ans=float('-inf')
heights=[0]+heights
dim=[0,1] #dimension=[height,length]
for i in range(1,len(heights)):
temp1=[heights[i],1] #vertical area considering the current bar only
temp2=[min(heights[i],dim[0]),dim[1]+1] #horizontal area
dim=temp1 if temp1[0]*temp1[1]>=temp2[0]*temp2[1] else temp2
ans=max(dim[0]*dim[1],ans)
return ans
only missed the id extension trick on pop ... hope that simply gets me a hint from the interviewer it I ever get this asked
Hey, love your videos.
Was stuck on this problem and rewrote your solution in ruby and broke down each part to understand it. It failed on test [2,1,2] which was 87/98. Looking through the comments of this video I saw someone suggested appending 0 to heights to prevent traversing the stack and this solution actually can pass [2,1,2]. Video might require a small update, just informing you.
Where did Neetcode learn these solutions?
Intuition -
• If current item is lesser than previous => pop the previous item
• Maintain a stack with 2 tuple => [index, height]
Playing the end at 0.5x while still trying to understand it and he's sounds drunk and saying " this is the most intuitive solution at least from my perspective " loll