LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@xingdi986]

Even with the video, this problem is still hard for me to understand and solve. but, anyway, thanks for explaining

[@Chansd5]

Samesies.

[@harpercfc_]

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!

[@ethanperry8]

When I see the monotonic stack tag on leetcode my hope of solving the problem dissipates

[@pl5778]

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

[@B3TheBand]

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]

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]

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

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

@@gorgolyt Cool. I'm a Software Engineer at Amazon. You?

[@fattysun1121]

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.

[@rishabharora2887]

All the best! :)

[@Thanos-hp1mw]

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.

[@abhilashpadmanabhan6096]

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

[@technophile_]

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 😮‍💨

[@protyaybanerjee5051]

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

[@justinUoL]

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

[@jackieli1724]

I agree with you

[@Ahmed.Shaikh]

Nah lc explanations of the 17th century were bangers.

[@gorgolyt]

LeetCode was founded in 2011. 🙄

[@xiaonanwang192]

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.

[@mandy1339]

Repetition really helps nail down the point into my head till it clicks. Liked and subscribed. Thank you!

[@chenhaibin2010]

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

[@JOP_Danninx]

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 👍

[@harishsn4866]

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

[@niraiarasu131]

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]

[@bchen1403]

Bumped into one of your earliest uploads and I am amazed at your progress. You improvements in tone is impressive!

[@tarunchabarwal7726]

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

[@gugolinyo]

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

[@ammarqureshi2155]

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

[@-_____-]

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]

how did you do that?

[@stella123www]

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

[@MaheshT101]

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

[@Rob-147]

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]

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

[@kunlintan6511]

Thanks! Your explaination helps a lot!

[@davidsha]

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

[@TechOnScreen]

ultimate solution! no other explanation can beat this.

[@rushilv4102]

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

[@B3TheBand]

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

[@abdulnarimanov2256]

best explanator in youtube

[@for_whom_the_bell_tolls]

Man you are the best across KZbin in this, by far!

[@80kg]

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

[@gregoryvan9474]

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

[@get_out_it]

first i didn't catch this solution but now i understand. You have topnotch skills.

[@chriss6114]

amazing algorithm and explanation. Really great solution you got.

[@suhaneemavar5573]

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.

[@n1724k]

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.

[@inderwool]

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.

[@DonTaldo]

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

[@Arunnn241]

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.

[@Arunnn241]

Not amortized o(n) in cases of duplicate heights however.

[@jingwenren8157]

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

[@gaurishaaaa]

with every video the respect for you just increases. Great work navdeep!

[@vietnamesedragonprince]

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;

[@therealg9542]

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

[@ygwg6145]

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.

[@binilg]

This was a hard problem for me and this video is the one which worked out best for me. Thanks for this video.

[@BloobUbloobok]

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

[@demaxl732]

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

[@jegadheeswarank6290]

Awesome explanation

[@JamesBond-mq7pd]

Thank you. So easy to write code after explanation.

[@konradhunter1407]

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

[@PallNPrash]

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

[@jasminehuang7748]

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]

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

[@jasminehuang7748]

@@krishivgubba2861 nope haha that's why i had to come here to see the solution

[@weraponpat1913]

Imagine if this is the coding interview problem that you need to solve under 1 hour for the job

[@sapnavats9105]

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

[@swagatochakraborty6043]

Intuition - • If current item is lesser than previous => pop the previous item • Maintain a stack with 2 tuple => [index, height]

[@cccccbgkv]

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

[@anujchoudhary5645]

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

[@kingKabali]

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

[@afzhalahmed1210]

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

[@JannibalForKing]

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

[@mapo5959]

how do you come up with this in an interview. just knowing monotonic stack isn't enough, must be legit einstein's cousin

[@aabhishek4911]

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

[@mwave3388]

Even SWEs usually get easy/medium leetcode questions. This is just for training. And I didn't understand the explanation.

[@Famelhaut]

the monotonic stack is genius

[@kunalkheeva]

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

[@adityatiwari2412]

Thanks for a clear explanation!

[@maganaluis92]

Great explanation.

[@securelyinsaycure]

Thank you Neetcode, this was helpful!

[@kucukozturk]

Thanks for the clear explanation.

[@yuchenwang-]

Thank you so so much!! I finally understand how to solve it

[@ruiqiliu3114]

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

[@gmhussein]

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

[@WorkAccountTalha]

beautiful drawing and great explanation!!!!!!

[@chits006]

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)

[@christopherconcepcion9000]

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.

[@ronniey4231]

beautiful drawing and explanation❤❤

[@Dom-zy1qy]

I came up with pretty much the same solution after a while, it just seems kind of "hacky" i guess. The lower difficulty leetcode problems seem to not really require this kind of solution. Although this algorithm definitely is more practical in the sense that you implement algorithms which require "more hands on behavior" like this in real projects. I can really appreciate when leetcode questions dont have esoteric hard to interpret / vague problem statements lol.

[@syafzal273]

I finally understood how to solve largest rectangle in histogram after watching this video

[@strayedaway19]

Awesome explanation, finally understood it.

[@MotleyVideos]

Thanks for the explanation with illustration!

[@deepanshuhardaha5750]

Just Amazing algorithm and explanation...Thank a lot

[@arthurmorgan332]

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

[@amruthammohan1667]

The best ever explaination ..💞

[@dhruvgarg722]

great explanation!

[@HieuVoPhamMinh]

we can eliminate the last loop by adding 0 by the end of heights, save few lines of code

[@yakovkemer5062]

Thank you for brilliant explanation

[@9Steff99]

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

[@KermitDominicano]

Makes sense, but there's no way I woulda figured this out in an interview without having seen the problem before lol

[@oneke4498]

9:42 THE STACK SHOULD CONTAIN 1 INSTEAD OF 0!!! There's no need to switching the index

[@srivatsansubramanian8535]

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

[@shubhankarsingh8456]

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

[@hrithikbandaru6462]

To omit the second iteration you can just append 0 to the heights and we should get the ans right away!!

[@chris.w391]

Append a 0 at the end of the heights can avoid iterate through the stack again.

[@ゾカリクゾ]

That may not be possible or might be expensive if the input is strictly an array of fixed length.

[@kalyankumar239]

I wish I have watched this a day early. it was asked in todays interview and I didn't do it.

[@soojy]

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

[@ericmei4151]

if you add a height of 0 at the end of the histogram instead of going through the stack again, it'll be more concise.

[@georgejoseph2601]

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

[@whonayem01]

Thanks NeetCode!

[@dera_ng]

Imagine if your Kryptonite was a leetcode question. Well, ladies and gentlemen, I present to you....

[@yinglll7411]

Thank you so much! This question bugged me…

[@fastlaner7746]

only missed the id extension trick on pop ... hope that simply gets me a hint from the interviewer it I ever get this asked

[@clementlin3140]

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

[@neelgandhi6672]

@NeetCode Hi! Good explanation of the stack approach. However, for time complexity, in worst case shouldn't it be O(N^2) ? Reason being there can be a case when the internal while loop (line 8-11 in your code) also runs N-1 times. Take this example: heights = [2,3,4,5,6,1] - In this case, when we are at index 5 (of height 1); the internal while loop of the code (to pop the higher height values) will be executed 5 times (which is N-1). - Since this while loop is nested inside the for loop; in worst case, for loop can take O(N) and while loop can take O(N-1). - This way, overall time complexity should be O(N^2) ? Please let me know what I might be missing.

[@NeetCode]

The total number of times the inside loop will execute is N, so time is actually O(N +N). Each value can only be added to stack once, and can only be popped once.

[@neelgandhi6672]

@@NeetCode Yes, on thinking more - that makes sense. It is O(N+N). Appreciate the quick response.

[@mugunthanramesh6854]

@NeetCode yes the complexity is O(n^2). consider arr = {2,3,4,5,6,1}. So In this case we will insert every element in the stack and when the last element is pushed all the other elements have to be poped right? so the complexity becomes O(n^2). Isn't 🤔

[@ゾカリクゾ]

@@mugunthanramesh6854 The inner loop pops the stack. You cannot pop more than N times in total since your stack will have N elements at most. You can think of it as distributing "N" pops over the big loop. In other words, the big loop takes O(N), and the popping also takes O(N). You can think of them separately, and add them up: O(N + N) = O(N).