LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python
HTML-код
- Опубликовано: 25 июл 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
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 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.
Bumped into one of your earliest uploads and I am amazed at your progress. You improvements in tone is impressive!
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
Repetition really helps nail down the point into my head till it clicks. Liked and subscribed. Thank you!
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?
What an intuitive way to handle the left boundary . Kudos!
man you are underrated, such a clear explanation. keep it up my guy!
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 watched couple of videos, but this one does the job :)
I like the intuition part to clear up why stack is being used, thanks!
Thanks! Your explaination helps a lot!
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!
Just awesome man, such a nice explanation! I needed only the first ten minutes to figure it out what I was missing
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
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. 🙄
amazing algorithm and explanation. Really great solution you got.
Blown away by the logic!
Thankyou for the clear and concise explanation.
Very clear explanation on the example!! Thank you very much!!👍
Wow. This is so intuitive. Thanks man, you're helping me out a lot!!
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?
You could use the trick to iterate for(int i = 0; i
very nice...Thanks for a detailed, clear explanation
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.
ultimate solution! no other explanation can beat this.
This is an excellent explanation! Thank you so much for these videos!
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.
Your explanation is so good, I didn't even have to look at the code solution!
This was a hard problem for me and this video is the one which worked out best for me. Thanks for this video.
Just Amazing algorithm and explanation...Thank a lot
Thank you so much for the video. You make hard questions easy
:)
Best explanation, helped a lot. Thanks a lot!!!
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 😮💨
with every video the respect for you just increases. Great work navdeep!
Thanks for the explanation with illustration!
Awesome explanation, finally understood it.
Thanks a lot buddy, you explanation was really good. 😘
Took me hours to get this one. Nice explanation NeetCode.
Thank you. So easy to write code after explanation.
great explanation!
Thank you so so much!! I finally understand how to solve it
first i didn't catch this solution but now i understand. You have topnotch skills.
Elegant and effective solution, explanation helped me to understand what am I missing in my way of thinking, thank you! 👍
Thanks!! Super helpful!
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....
Great explanation.
Thank you for brilliant explanation
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 for the clear explanation.
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.
Thanks for a clear explanation!
So well explained!
Great explanation!!
best explanator in youtube
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.
The best ever explaination ..💞
Thanks NeetCode!
Amazing explanation！
beautiful drawing and great explanation!!!!!!
A super hard problem...but good explanation, thx 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
The Best explanation but I needed the solution in java. Thank you anyways.
I was so close to solving my first hard problem, One day i will become just as good as this guy
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]
keep them videos coming
Awesome explanation
thanks man you are the best
अद्भुत, अकल्पनीय, अविश्वसनीय
beautiful drawing and explanation❤❤
thank you so much !
Thanks Man!
good content!
@NeetCode what keyboard & switch are you using? the clacky sound as you type is so satisfying. And thanks for the excellent content!
Thanks!
I used recursion and partitioning by the min element. It worked but was too slow for large lists.
Do you mind mentioning what kind of whiteboarding software and hardware you use .
With diagrams, it's very intuitive.
Finally, thanks!
great, thanks
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
Thank you so much! This question bugged me…
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
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
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
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.
perfect. just... perfect.
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.
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)
Bro..... you're so smart!
I wish I have watched this a day early. it was asked in todays interview and I didn't do it.
When will you upload solution for maximal rectangle Problm
Imagine if this is the coding interview problem that you need to solve under 1 hour for the job
thanks
how is enumerate diff from range
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.
the monotonic stack is genius