LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python
Vložit
- čas přidán 12. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/largest-...
0:00 - Intuition
5:44 - Conceptual Algorithm
13:58 - Coding optimal solution
#Coding #Programming #CodingInterview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
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!
Hey folks, I usually take notes by flagging the solution at various points for these kinds of problems and I will share them below, hope it helps
Solution:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = [ ] # pairs of index as well as heights
for i, h in enumerate(heights):
start = i # originally the start will be the current index of the height
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max( maxArea, height*( i-index )) # Note 1
start = index # Note 2
stack.append( (start, h) ) # Note 3
for i, h in stack:
maxArea = max( maxArea, h * ( len(heights) - i )) # Note 4
return maxArea
Notes:
For this problem we need to create a stack where we keep track of the heights as they appear along with their indexes
Intuition:
There can be multiple possible bars that can be formed in the histogram by combining them together. To find the bar that has the largest area possible we need to find the bars that can extend vertically and horizontally as far as possible.
Some bars have the limitations on either sides so they cannot be extended horizontally, if they have bars that are shorter than them on either side, this will prevent them from having area beyond the shorter bars ( horizontally )
Algorithm:
We use the enumerate function to traverse through the heights array, it will give us the index ( which will be used for calculating the width of the bar ) as well as the corresponding heights
The " start " variable keeps track of the index where the bar's width will be
At first the stack will be empty so we will append the values of " start " variable and current height in the stack
However for each iteration in the while loop we will check whether our stack contains anything, if it does then we will retrieve the value on the top of our stack and check if the height is greater than the current, if it is then we will pop that element from the stack and retrieve the index as well as the height that was stored in the stack
Now using these values of index, height we will calculate the area
Note 1:
( i - index )
The reason we do this is for calculating width is because the current height ( ith height ) we are at is less than the one that was stored in the stack. This means that the height that was stored in the stack cannot extend on the right side any more ( because the height of the bar on it's right side is lower than itself )
The " index " is essentially the starting point of the bar whose values we popped from the stack
The difference between the two will give us the width of the bar
Note 2:
We update the start variable to the index because the current bar being shorter than the previous means we can extend it to the left side
Note 3:
We append the two values in the stack, " start " and the height
" start " is essentially the index from where the width of the bar can be calculated
Note 4:
We need to calculate the areas of the bars which are left in the stack
The width of these bars is calculated by subtracting the index where their width starts from the total length
We use total length because the shorter bars are essentially the ones that are able to extend on both sides because they are surrounded by bars that are longer than them
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
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?
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 👍
Bumped into one of your earliest uploads and I am amazed at your progress. You improvements in tone is impressive!
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.
What an intuitive way to handle the left boundary . Kudos!
Repetition really helps nail down the point into my head till it clicks. Liked and subscribed. Thank you!
I watched couple of videos, but this one does the job :)
man you are underrated, such a clear explanation. keep it up my guy!
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. 🙄
Such a clever solution with minimal usage of extra space and minimal function calls. Love it.
This is the best explanation I found for this problem. Thank you
Thank you for the most clear explanation and code as always!
I like the intuition part to clear up why stack is being used, thanks!
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
Thanks! Your explaination helps a lot!
amazing algorithm and explanation. Really great solution you got.
Just awesome man, such a nice explanation! I needed only the first ten minutes to figure it out what I was missing
Blown away by the logic!
Thankyou for the clear and concise explanation.
Very clear explanation on the example!! Thank you very much!!👍
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?
Wow. This is so intuitive. Thanks man, you're helping me out a lot!!
ultimate solution! no other explanation can beat this.
very nice...Thanks for a detailed, clear explanation
Just Amazing algorithm and explanation...Thank a lot
Your explanation is so good, I didn't even have to look at the code solution!
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.
You could use the trick to iterate for(int i = 0; i
This was a hard problem for me and this video is the one which worked out best for me. Thanks for this video.
This is an excellent explanation! Thank you so much for these videos!
Thank you so much for the video. You make hard questions easy
:)
Awesome explanation, finally understood it.
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.
Best explanation, helped a lot. Thanks a lot!!!
with every video the respect for you just increases. Great work navdeep!
Thanks a lot buddy, you explanation was really good. 😘
Thanks for the explanation with illustration!
Thank you. So easy to write code after explanation.
great explanation!
first i didn't catch this solution but now i understand. You have topnotch skills.
Thank you so so much!! I finally understand how to solve it
Took me hours to get this one. Nice explanation NeetCode.
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.
Elegant and effective solution, explanation helped me to understand what am I missing in my way of thinking, thank you! 👍
Great explanation.
Thank you for brilliant explanation
Thanks for a clear explanation!
Thanks for the clear explanation.
Thanks!! Super helpful!
best explanator in youtube
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 😮💨
So well explained!
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.
Thanks NeetCode!
Amazing explanation！
Great explanation!!
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....
The best ever explaination ..💞
A super hard problem...but good explanation, thx so much.
The Best explanation but I needed the solution in java. Thank you anyways.
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]
अद्भुत, अकल्पनीय, अविश्वसनीय
beautiful drawing and great explanation!!!!!!
keep them videos coming
thanks man you are the best
Awesome explanation
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.
thank you so much !
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
Thanks!
Thanks Man!
beautiful drawing and explanation❤❤
great, thanks
good content!
I was so close to solving my first hard problem, One day i will become just as good as this guy
@NeetCode what keyboard & switch are you using? the clacky sound as you type is so satisfying. And thanks for the excellent content!
Finally, thanks!
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
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.
I used recursion and partitioning by the min element. It worked but was too slow for large lists.
Imagine if this is the coding interview problem that you need to solve under 1 hour for the job
I get it every time I watch it and then I forget it after a few weeks, lmao
perfect. just... perfect.
thank you
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
Got it!!
Thank you so much! This question bugged me…
Bro..... you're so smart!
thanks
Very good explanation and great solution! On another note, what do you use to make you drawings?
@@NeetCode Do you use the mouse as drawing device or a pen? And if you use a pen, which one?
@@anmatr i could hear mouse clicks for everything he drew in this video. Not sure if some pens make the same clicking sound as well
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)
the monotonic stack is genius
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.
7:40 I was wow!
I would love to have a hint for each problem what the runtime of the optimal solution is, so I can know if my solution is optimal without looking at the sample solution
I wish I have watched this a day early. it was asked in todays interview and I didn't do it.
Do you mind mentioning what kind of whiteboarding software and hardware you use .
With diagrams, it's very intuitive.