Largest Rectangle in a Histogram - Coding Interview Question

Check out the detailed data structures and algorithms course at www.interviewa... !
Largest Rectangle Under A Histogram
Today's problem is about finding the largest rectangle within a histogram. We'll explore a linear time solution.
I encourage you to try and solve this problem before looking at the video. Then post your solution below.
I give you two options toward the end of the video, so let me know which problem you'd like covered next.
If you want to learn data structures and algorithms, visit eepurl.com/dhWjSH and sign up to learn about my upcoming course.

[@missyalyssi]

Yes I needed a chanel like this where someone goes through their entire thought process really showing how they get through an interview. Not some short video where they magically know the answer after 10 minutes.

[@claahiaxmedclaahaxmed8912]

A Morgan 😂😆

[@sakshishah6059]

Too good explanation but just a correction it will be if(stack.isEmpty() || hist[stack.peek()

[@jlk665]

if(stack.isEmpty || hist[stack.peek()]

[@garaidebasish]

right. I thought he was going to correct it at the end. The issue is his indexes are equal to the value of the elements.

[@ArpitDhamija]

@@garaidebasish yes i also have a doubt on it

[@AhmedAli-jx9ie]

he already mentioned we are storing indexes

[@lakshithnishshanke7245]

here u have to compare values. right. Previous index will always be lesser than the current index

[@varunnarayanan8720]

Man. This guy is legendary.I exactly watched only till 7.25 and got the logic . He derives the logic and doesn't throw it at your face. Wow!

[@Garentei]

It's wrong though.

[@NeetCode]

I can't link it, but I've made a video for this problem that is MUCH MORE intuitive and might be helpful for some people. =D​

[@devaentgs9957]

Reference to your video kzbin.info/www/bejne/sKmYhKpvZphjgpI

[@lakshithnishshanke7245]

this whole algorithm is a mess. ye he explains it quite good. But this is not a correct solution correction := stack.isEmpty() ? i : i - 1 - stack.peek() instead of stack.isEmpty() ? i-1 : i - 1 - stack.peek() difference is u must use [i] instead of [i-1]

[@dwaipayanbarman5194]

The pseudo code is wrong in many places

[@ujurak3899]

What he has is correct. i is incremented in the if-block.

[@kant.shashi]

@@ujurak3899 www.geeksforgeeks.org/largest-rectangle-under-histogram/ whenever after removing the top, if stack is empty it essentially means everything on the left from starting index 0 has atleast this height of popped element. So we should calculate entire area from start Index(0) to the popped element/bar(including) which is (i-1) - (0) + 1 = i

[@Rohankumar-wh3uu]

Nice explanation :) Correction - "hist[stack.peek()]

[@eduardgiovannyariasrincon6635]

The Logic fails with this example: hist = [11,11,10,10,10] I think the problem is that when the stack gets empty before reaching the end. That means, you find a height that is the lowest height till that point, making the stack empty.

[@akarshrastogi3682]

You just did a damn good job of explaining everything so intuitively. Just after watching your explanations, I go and write code directly for a problem without hesitation, and it would work right away ! Please continue making videos, I'm very sure there are no people on YT who explain things this well.

[@3992Amit]

Great solution! Just one tiny correction in the solution. Since we push the index into the stack and not the height of the histogram, when you're pushing index into the stack, you are comparing the index with the height of the histogram. "st.peek()

[@pawanthapa6596]

yeah! same thought.....we need to check if the value at index( given by top of stack) is less than or equal to the next value in the array....only then we push the next index

[@asrahal2520]

i am also searching for the same thing in the comments

[@sandeshverma517]

The only vedio worth investing 24 min and now i can feel this algorithm

[@ujjvalsharma5055]

great teaching method. Far better than others.

[@darshantsdarshan1]

Folks, get the logic and thought process, and code by yourself! Irfan, thanks for the video!

[@adityabhandari6688]

watched this video twice and it worked for me

[@WikiPeoples]

What a great video. I actually really liked that you had a student with you, asking questions. It often provided a nice natural pause, where you could think about the problem too. Often her question was something I was thinking as well. Or if it wasn't, it was a thoughtful questions that helped me understand the problem better... More than 1 student might be too many questions, but just 1 was excellent addition to this video.

[@VladimirDjokic]

I like your realistic approach

[@laxminarain2843]

nice way of teaching sir...I appreciate this, keep going on and let every other teachers in college specially in india get to know how to teach the concept of Dynamic programming

[@anshulms]

Learnt some where for yourself - explained to yourself and then put together a video for your self.

[@ajaypilaniya8562]

Hey, your code has a major issue? Try running it for 2 2 2 2 2, your code will give output as 8 while it should be 10. To avoid this define area like this- int area=(st.empty()) ? hist[currMax]*i:hist[currMax]*(st.empty()? i-1:i-1-st.top());

[@rudra-thandavam]

I am getting 10. Not 8.

[@deepaksingh5607]

Explained it quite well.

[@vaibhavsomani3733]

Hello Irfan, really nice video and explanation of the concept. Just one minor change in the else condition and second while loop. The change is: s.isEmpty() ? i : i - 1 - s.peek() Instead of i - 1, it should just be i as i - 1 will give the area as 0, when we will calculate for first column.

[@ericmiller3231]

I really like the way you let us see you talk through the problem in these vidoes. Thanks! Question: Are you sure the single stack implementation you're using is O(n)? I think in the worst case you have steadily climbing bars, so every element looks through every other element (ie: while(stack.peek())?

[@manishsharma-cb9yw]

there`s a flaw you when the stack is empty you should use width as ( i) instead of( i-1) because this time we don't have to go one place before next occuring element hence the width of this rectangle would be i.

[@marriagedance8657]

Really Good explanation. I don't find the reason behond so many dislikes

[@sajadkarim]

Thanks for the video.. Solution is quite simple if we arrange the bars... e.g. 1x8 = 8 (bar-1 can be shared by all the 8 bars) 2x7 = 14 (bar-2 can be shared by remaining 7 bars) 3x5 = 15 4x2 = 8 5x1 = 5

[@sarabahaadini5699]

In the case that stack is empty, it the width is "i" not "i-1"

[@AdityaNMurthy]

You're correct. It took me some time to debug and find the issue.

[@kumarsatyam5218]

you are going back, not the index but to reduce the stack everytime you hit a smaller value.If you get the one smallest values at n-1 posttion then you are eventually going dig to into stack till the first value. Also consider the cases, where u have only incremental values and no decreamental, it would be eventually O(n^2) solution.

[@balaganesh3440]

The best explanation!

[@deepamgupta8011]

I always want to feel to see the solution working in my mind with images. Going through the thought process, a very unique way to achieve the same. Thanks a lot.

[@itzcs1861]

This video is awesome. while watching it , not even half , i got the idea to solve this myself. nice way of approach.

[@ContortionistIX]

Here's a slow solution in Python: def largestRectangleInHistogram(array): largestRectangle = 0 for i in range(len(array)): positiveCounter = negativeCounter = 1 while i + positiveCounter < len(array) and array[i + positiveCounter] >= array[i]: positiveCounter += 1 while i - negativeCounter >= 0 and array[i - negativeCounter] >= array[i]: negativeCounter += 1 largestRectangle = max(largestRectangle, array[i] * (positiveCounter + negativeCounter - 1)) return largestRectangle

[@Garentei]

Is this algorithm even correct? Let's take a look at [2, 1, 2]. Your algorithm first adds 2 to the stack, so the stack looks like this: [0]. Then it looks at 1, since 1 is < than 2, 2 gets deleted from the stack and our current maximum is (1 * 2), stack now looks like this: [1]. Now we are looking at 2, since 2 is >= than 1, let's add it to the stack and keep going; stack looks like this [1, 2]. Now, let's end the algorithm: 2 is removed from the stack and we calculate (1 * 2), 1 is removed from the stack and we calculate (2 * 1), stack is now empty. The maximum rectangle area is 2, but it is actually 3. The problem with this approach is that is completely discards previous heights that could be useful later on, an example would be this would be the first height in [2, 1, 2] which was savagely thrown out just because the next element is smaller than it, even though it would later be useful to combine it with the last element...

[@sakshishah6059]

No it works you can run and see the output... Also make a small change: One more correction is that in else it will be like (stack.isEmpty()?i:i-1-s.peek())

[@jaatharsh]

Thanks, Irfan - your explanation to approach was quite useful.

[@akarshrastogi3682]

Great Video. You earned a subscriber in just one video. Your videos are really fun to watch at 2x. Although it should be just i instead of i-1 when the stack is empty while calculating area.

[@silentgrove7670]

def histogram_find_largest_rectangle(bars): bars.sort() maximum=0 for i in range(len(bars)): x=bars[i]*(len(bars)-i) if x>maximum: maximum=x return maximum %timeit -n100 histogram_find_largest_rectangle(random.sample(range(10000), 10000)) 17.9 ms ± 727 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) code from video: (i used closest python codes for it) def maxarea(hist): stack=[] maxi=0 i=0 while i < len(hist): if stack==[] or stack[-1]maxi: maxi=area while len(stack)>0: currmax=stack.pop() area=hist[currmax]* i if len(stack)==0 else (i-1-stack[-1]) if area >maxi: maxi=area return maxi %timeit -n100 maxarea(random.sample(range(10000), 10000)) 24.9 ms ± 1.65 ms per loop (mean ± std. dev. of 7 runs, 100 loops each) I didn't see any speed improvement over just a simple iteration after a sort. Perhaps I am missing something.

[@josephluce7281]

order matters in this question, you can't sort it, it doesn't work.

[@vishalgandhi123]

Does this approach works for 2,1,2 histogram ?? This should return 3 as a max rectangle area but with this approach, its coming as a 2...

[@utsavprabhakar5072]

should be i when stack is empty. I recommend not to depend on he source code here, in the interview handling these testcases are really tough. So hats off to irfan for showing us the intuition behind it. please refer to leetcode or g4g for the correct solution.

[@MengJiun_Chiou]

Exactly. I followed his idea and implemented myself and it turned out that I couldn't pass the test case [2,1,2]. The trick is, instead of using the index returning by poping the top element, we use the index of the one more previous element (and then plus 1). This also corresponds to initializing the stack as [-1] so that it computes the area with the length of the whole array.

[@Garentei]

@@utsavprabhakar5072 Why bother making a video when the whole logic is wrong? If it doesn't' work it doesn't work. It's just a waste of time to learn incorrect algorithms.

[@josephluce7281]

Code doesn't work if the input is descending. [3,2,1] or [2,1,2]

[@keshavdaga9974]

it works

[@Garentei]

@@keshavdaga9974 It doesn't though.

[@fursletanck9037]

i think this works too (in python): ar=[] R=[] x=0 while True: try: x=int(input(": ")) ar.append(x) except: break for i in range(1,max(ar)+1): t=0 for k in range(0,len(ar)): if ar[k] < i: t=0 continue R.append((t+1)*i) t=t+1 print(ar) print(max(ar)) print(R) print(max(R))

[@SushilKumar-wt7js]

Hey Man! ........ your teaching process is gr8 !

[@chypsdchypsd8716]

awesome Please make more videos like this

[@sameerawasekar7305]

One minor correction, if the stack is empty, int area=hist[currMax]*i

[@rrjishan]

brillliaaaantttttttt! thanks a lot sir !

[@bensmith9253]

Another great video. Subbed & really looking forward to working through all the vids on your channel

[@frontendwebdeveloper1442]

A correct Java Solution for anyone who wants to see: import java.util.*; class largestRectangle{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println("Enter the array of histogram ?"); String inp[]=sc.nextLine().split(" "); int hist[]= new int[inp.length]; for(int i=0;i= 0 && height[p] >= height[i]) { p = lessFromLeft[p]; } lessFromLeft[i] = p; } for (int i = height.length - 2; i >= 0; i--) { int p = i + 1; while (p < height.length && height[p] >= height[i]) { p = lessFromRight[p]; } lessFromRight[i] = p; } int maxArea = 0; for (int i = 0; i < height.length; i++) { maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1)); } return maxArea; } }

[@chandanagubbiparamesha904]

finally understood after watching your video..thanks

[@kaichenghu3826]

Subscribed! Really explained this question well. Please keep the good work.

[@wanwan6234]

how about [2,12]?it seems not work .

[@lkzhao6339]

The question is what he illustrates is just about a first ascending then decending sequence. What if there are several ascending and decending after the first one in randomness. Would the algorithm still be correct?

[@davidhanover8224]

for videos like this you should probably step away for at least a few seconds and let the viewer see the white board.... you're blocking the code in all the ending shots

[@MrThepratik]

well explained.

[@stanyang95]

The index of the code is wrong, cause we have increased i to the next value(which is smaller than the currMax), thus if the stack is empty, the width of it should be i(beacause the currMax's index is i-1, the width of it is i -1 +1 which is i, we count index from 0, that's why we need to add 1)

[@rahulsharma-cb7kk]

Excellent work

[@YasasCPerera]

what if the histogram has only one column ? in the first while loop index 0 will be added to the stack and increment i to 1. in the second while loop, currMax = 0; int multiplier = (stack.empty()) ? (i-1) : (i -1 - s.top()); // since stack is empty, multiplier is 0 so below calculation is zero. int area = hist[currMax]*multiplier;

[@IrfanBaqui]

Looks like an off-by-one error. Good catch. I should really go through the testing process too in these videos. I leave it out because the video is quite long already, but testing is an important component of a coding interview.

[@YasasCPerera]

no problem. I have gone through many of your videos and they are awesome. they really help me to adjust the thinking pattern. thanks a lot.

[@bauyrzhanmaksot3022]

I guess it is better use while(!stack.isEmpty()) instead of while(stack.peek()) (at least in Java). Also, I think that the mistakes he has done actually helps to understand the problem. You start to analyze yourself and train your brain =)

[@punitoza84]

Very nicely explained, thank you!

[@juanperusquia7456]

His solution fails with this input: [3,1,2,3,1]

[@rudra-thandavam]

5 should be the answer and still is 5 with his algorithm.

[@nikhilgupta71]

superb!

[@serhiypidkuyko4206]

Hi, Irfan. Thank you for the task and the proposed solution based on using a stack. However this problem has a simpler solution (one can easily calculate the "next" rectangle from the previous one)

[@ankitgirdhar2238]

beautiful explaination. thanks a lot bro

[@untangledyogi4864]

will this work for the arr{2,3,6,2,7,3}?

[@rishikakkar4510]

I think There is a way t do it by thinking that finding the same height and adding all the number of bars you have crossed and then finding the area of the rectangle that you have identified and doing it until max area is obtained

[@riteshdes]

It should have hist[stack.peek()] < hist[I[ in the first condition.

[@sumandas829]

Yeah boi

[@dipteshsil9299]

Hi Irfan, What is the complexity of the solution? Isn't it n^2 only?

[@nothinrandom]

Interesting approach. For something like this, could we possibly sort the histogram values first from low to high? So [1,2,3,4,5,3,3,2] becomes [1,2,2,3,3,3,4,5]. Then use a for loop to decrement. int max = 0; int width = 0; int length = array.length; for(int i = length; i>0; i--) { width++; // assuming width of 1 in video if(array[i-1]*width > max) // assuming index 0 { max = array[i-1]*width; // max value gets updated } else { break; } }

[@souravsarker9100]

basically no. try this case, [4,5,1,7,6] , answer should be 12.

[@nothinrandom]

good callout. works if you could sort it though

[@semalsherathia1034]

I have a solution that is O(nlogn) but i don't know whether it is correct? Approach is to iterate through all elements till there is no element bigger than the current element and we Calculate its max area to be that max element*1 = element itself. So we know that there is no element greater than this element one right side of hostogram. But on the left side there are 2 possibilities. Whether element to the left is equal to the current element or is smaller in height. We can perform binary search to find the index of element where it's height is less than that of current element and we got width (current position - index we foind) and height is the current element. Now we update the max answer and keep on doing till the end of Array! Can anyone tell me whether this approach is feasible or not?

[@manjitsinghthakurratan6723]

Why cant we do this ? run two pointers (i,j) from 0 to length-1 & length -1 to 0 and calculate area as Min(i,j)*(j-i) and then move the i or j based on arr[i]arr[j] and keep track of max area. Do this till i

[@dineshkumarsahu9997]

Very nice video

[@dumbcurious450]

plz add more videos of leet code pblms ..

[@bhalinder3801]

Att veere

[@Tea-Spin]

Maybe a suggestion, make the volume of the "interviewer" voice slightly bigger. It's kinda hard to hear. Anyway, nice video.

[@IrfanBaqui]

Thanks for the feedback

[@RahulSingh-ex2sm]

BEST on whole INTERNET!

[@reethikavanaparthy6984]

Very nice explanation thanks a lot:)

[@mayankgupta2543]

it looks from code that pushing onto stack will happen only once as long as the condition meets(as in example, it will happen in the beginning ), but at the time of analysis we have seen that pushing on to stack will happen two times(for bars with index 5, 6) , any clue??

[@nirajmotiani]

you can merge the else and while part into one

[@akkzhol1]

Bro, are you ok? 2 years nothing uploaded

[@avineshbenjamin1782]

Awesome explanation! can you do a video for Painters Problem or Kth number found using Binary search only

[@tacowilco7515]

Why did you decide to use stack. Your whole explanation implied recursive function. In my opinion, recursive function would be so much more straightforward.

[@chrisliu5403]

great video, really helpful

[@tanmayagarwal8513]

Somebody pls explain that why did we use another while loop inside the first one?

[@MrKreidel]

I think the code doesn't work for other histogram shapes than this, e.g. multiple peaks and many other shapes. Has anyone got a good idea on a nice algorithm? Obviously the "brute force" version would work. (i.e. for each column count the righthand neighbors that are at least equal height, and multiply that count by the own height. And then remember the result as maxvalue if it is bigger than the previous maxvalue.). Small optimizations are possible, e.g. "disabling" all visited columns that are of equal height than seen before, so that we can skip them in the iteration. But still my gut feeling says that there must be a better solution. Any ideas ? :-)

[@DharmendraSingh-vy3if]

good job

[@thewaymakerofficial]

toooooo goooooood bro welll work...

[@vasudev9496]

Are you learning or Teaching?

[@just4uchin]

Superb!

[@kalpkumudkumar8163]

this best video on the You tube on this problem .... you need more subscribers ... thanks !!!

[@saipanda893]

How i get your previous problem?which were send by you in email.

[@nackyding]

Nice!

[@jonathanp6739]

This actually fails for a histogram of - 5,5,5,5,1,1,1,1

[@RahulVatsTWI]

it shouldn't be stack.peek()

[@smolboii1183]

my solution :0 from collections import deque def largest_rect(hist): max_height = max(hist) barricades = {} # stores indexes of 'barricades' (bars with height one smaller) for each height for height in range(1,max_height+1): barricades[height] = [] for i, h in enumerate(hist): if h == height-1: barricades[height].append(i) rects = deque([(0, len(hist)-1)]) # index of starts and ends of current rects largest_area = 0 curr_height = 1 while curr_height

[@souravsarker9100]

@irfan Thanks, bro. Nice explanation. Please try to make N Queen.

[@hc2cox]

Won't work for bimodal

[@yogeshdeveloper5346]

Can we do it like this: (Please judge me) 1. Create an empty hashmap 2. Iterate over the array of bar heights. 3. Check whether the height of bar is present in our hashtable, if not create it like {height: [index of height in array]}. If it's created then we will append the index of it in the respective key's value (array). Once we have done preparing the table like {1: [0], 3: [2, 5, 6]},...} 4. Iterate over the table to get largest array as value. 5. Calculate the area by height*(difference of first & last element of that largest array) Am I correct?

[@VishnuPrateekK]

how to store dimensions of the max area rectangle.

[@kahizer]

this algorithm seems a lil too complex. I think using two pointers would give you a cleaner algorithm something like this.. public static int LargestAreaHistogram(int[] histogram) { int result = 0; var i = 0; var j = histogram.Length - 1; while(i < j) { var area = ((j - i) + 1) * Math.Min(histogram[i], histogram[j]); result = Math.Max(result, area); if (histogram[i] < histogram[j]) i++; else j--; } return result; }

[@rafael_madureira]

This solution doesn't work with a histogram like this one [ 6, 2, 5, 4, 5, 1, 6 ] The correct answer is 12, but this algorithm displays 42 :(

[@gokukakarot6323]

This is like LOG_LEVEL=debug

[@Orniflyer]

here's how I'd do it function largestRectAreaInHistogram(arr) { return Math.max(...Array(Math.max(...arr)).fill(0).map((_, row) => arr.filter(value => value >= row).length * row )) }

[@abhisheksa9552]

Took a little longer to understand fully

[@01theprinceway]

doesnt' work for [4, 2, 3, 4]

[@sunilsarode4295]

c++ code with same logic int largestRectangleArea(vector& heights) { stack st; //we create stack to store the index int n=heights.size(); int i=0; int maxarea=0; while(i=heights[st.top()]){ st.push(i); i++;//we increament i here only and not at other place //cout