Largest Rectangle in a Histogram - Coding Interview Question 

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.

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!

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​

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]

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

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.

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

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.

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

watched this video twice and it worked for me

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.

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

great teaching method. Far better than others.

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

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

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

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.

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

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())?

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

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.

I like your realistic approach

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

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.

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.

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

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

Explained it quite well.

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.

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());

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

awesome Please make more videos like this

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

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

finally understood after watching your video..thanks

well explained.

The best explanation!

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

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

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?

beautiful explaination. thanks a lot bro

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

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

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

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)

plz add more videos of leet code pblms ..

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

Very nicely explained, thank you!

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.

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?

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

superb!

One more correction is that in else it will be like (stack.isEmpty()?i:i-1-s.peek())

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;

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

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

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)

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

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

Excellent work

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

you can merge the else and while part into one

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

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

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

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

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?

Very nice explanation thanks a lot:)

brillliaaaantttttttt! thanks a lot sir !

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

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; } }

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

great video, really helpful

Very nice video

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

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

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; } }

BEST on whole INTERNET!

Superb!

Att veere

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

toooooo goooooood bro welll work...

good job

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

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

package com.coding; public class Histogram { public static int findMaxAreaInHistogram(int[] hist) { int areaMax = 0; int len = hist.length; if (len 0 && j >= 0; j--) { if (hist[j] < hist[i]) { if (hist[j]

Nice!

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

how to store dimensions of the max area rectangle.

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

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

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

This is like LOG_LEVEL=debug

Won't work for bimodal

Stack is not very clear in the interview, try this one leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)

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

Are you learning or Teaching?

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

it shouldn't be stack.peek()

Took a little longer to understand fully