🚀 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

@Chansd5

2 жыл бұрын

Samesies.

@harpercfc_

2 жыл бұрын

feel a little bit relieved seeing your comment :( it is so hard

@chaoluncai4300

Жыл бұрын

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:))

@carl_84

Жыл бұрын

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!

@Mustafa-099

Жыл бұрын

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. :)

@carl_84

Жыл бұрын

This is done in Elements of Programming Interviews in Python book.

@kobebyrant9483

Жыл бұрын

to be honest, I found solution in the video is more intuitive and easier to understand

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!

this is awesome. I don't know how someone can come up with the solution in an interview for the first time.

@B3TheBand

7 ай бұрын

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.

@eloinpuga

4 ай бұрын

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.

@B3TheBand

4 ай бұрын

@@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.

@gorgolyt

3 ай бұрын

@@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.

@B3TheBand

3 ай бұрын

@@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!

What an intuitive way to handle the left boundary . Kudos!

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.

Such a clever solution with minimal usage of extra space and minimal function calls. Love it.

man you are underrated, such a clear explanation. keep it up my guy!

I like the intuition part to clear up why stack is being used, thanks!

Just awesome man, such a nice explanation! I needed only the first ten minutes to figure it out what I was missing

This is the best explanation I found for this problem. Thank you

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

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.

sincerely the best explanation for lc questions in 21st century. thank you!

@jackieli1724

Жыл бұрын

I agree with you

@Ahmed.Shaikh

7 ай бұрын

Nah lc explanations of the 17th century were bangers.

@gorgolyt

3 ай бұрын

LeetCode was founded in 2011. 🙄

Thank you for the most clear explanation and code as always!

I watched couple of videos, but this one does the job :)

Blown away by the logic! Thankyou for the clear and concise explanation.

Thanks! Your explaination helps a lot!

amazing algorithm and explanation. Really great solution you got.

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.

@hakimamarouche9185

7 ай бұрын

how did you do that?

Wow. This is so intuitive. Thanks man, you're helping me out a lot!!

Very clear explanation on the example!! Thank you very much!!👍

You could use the trick to iterate for(int i = 0; i

Your explanation is so good, I didn't even have to look at the code solution!

ultimate solution! no other explanation can beat this.

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 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.

very nice...Thanks for a detailed, clear explanation

This is an excellent explanation! Thank you so much for these videos!

Thank you so much for the video. You make hard questions easy :)

Just Amazing algorithm and explanation...Thank 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!

Best explanation, helped a lot. Thanks a lot!!!

Awesome explanation, finally understood it.

Took me hours to get this one. Nice explanation NeetCode.

Thanks a lot buddy, you explanation was really good. 😘

Thank you. So easy to write code after 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.

great explanation!

Elegant and effective solution, explanation helped me to understand what am I missing in my way of thinking, thank you! 👍

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!!!

@cgcrack4672

11 ай бұрын

I was able to come up with brute force and the test cases are like 87, can you please share your approach.

Thanks for the clear explanation.

Thanks!! Super helpful!

best explanator in youtube

Thanks for a clear explanation!

Great explanation.

So well explained!

Thank you for brilliant 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.

@NeetCode what keyboard & switch are you using? the clacky sound as you type is so satisfying. And thanks for the excellent content!

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....

Thanks NeetCode!

Great explanation!!

Amazing explanation！

A super hard problem...but good explanation, thx so much.

keep them videos coming

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.

अद्भुत, अकल्पनीय, अविश्वसनीय

The best ever explaination ..💞

Awesome explanation

beautiful drawing and great explanation!!!!!!

I was so close to solving my first hard problem, One day i will become just as good as this guy

thanks man you are the best

Thanks Man!

The Best explanation but I needed the solution in java. Thank you anyways.

thank you so much !

Do you mind mentioning what kind of whiteboarding software and hardware you use . With diagrams, it's very intuitive.

good content!

Thanks!

Finally, thanks!

great, thanks

beautiful drawing and explanation❤❤

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

I used recursion and partitioning by the min element. It worked but was too slow for large lists.

Thank you so much! This question bugged me…

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]

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

@krishivgubba2861

3 ай бұрын

i did the same thing but got a time limit exceeded error on leetcode. did your solution pass?

@jasminehuang7748

3 ай бұрын

@@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

@aabhishek4911

2 жыл бұрын

you cant do this in an interview unless you know the answer , or as you said you must have einsteins genes

@mwave3388

2 жыл бұрын

Even SWEs usually get easy/medium leetcode questions. This is just for training. And I didn't understand the 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

perfect. just... perfect.

Very good explanation and great solution! On another note, what do you use to make you drawings?

@anmatr

3 жыл бұрын

@@NeetCode Do you use the mouse as drawing device or a pen? And if you use a pen, which one?

@ohyash

2 жыл бұрын

@@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

thank you

the monotonic stack is genius

Bro..... you're so smart!

I didnt understant anything at all. at 12:04, how do you get the beginning and ending values for the rectangle of height 2? where did you save that it bagan at 1?

@Sinders

7 ай бұрын

every time you pop an element from the stack, you're setting the index of the current element to that. For the rectangle of height 2, we initially pop 6 off the stack, which was index 3 (then set the current index to 3), then we pop the 5 off the stack which is index 2 (and set the current index to 2). now the next thing on the stack we can't pop off (as 2 > 1), so the index remains whatever the index of 5 was, so index 2. let me know if you still dont understand

I get it every time I watch it and then I forget it after a few weeks, lmao

This question is basically a monotonic stack with a bit of twist to it

When will you upload solution for maximal rectangle Problm

My only doubt is, shouldn't it be i - index +1 at the end of line 10? if a rectangle extends from say index 0 to 1, i - index should only return 1 when it should be 2..

thanks

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.

Got 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.

@zokalyx

11 ай бұрын

We don't necessarily have the option to add elements to the input, especially if it's a fixed size array (C / Java)