Largest Rectangle in a Histogram - Coding Interview Question

hey guys I'm covering a very popular problem this week and it's about finding the largest rectangle inside of a histogram so it may seem complicated at first but I go through my entire thought process and you'll see at the end how simple the solution is so also let me know in the comment section below what you think of the solution and if you have your own solutions so let's dive right into it so we are given a histogram that looks something like this and we have to find the maximum rectangular area within it okay so let's look at this example we have an array that you translated into a histogram over here right so just a few questions on it all of these numbers over here they correspond to the heights of these bars yeah and what about the width so that constant right unit one okay so let's say the widths are just one unit for all of these so let's see how I would do it the first thing that comes to mind is that I would iterate through this entire array for each index out see that what are what are its neighbors so let me just give you an example let's say I am at 3 right I'm at reading the array and I I'm done with Prior indices I'm at 3 right now and then for this index I'll say okay what are the values to my right and I will go all the way till the next value is less than me right so let's say over here I stop right there right and I'll do the same thing what are the values to my left and I'll go all the way till some value the next value is less than me so I'll stop right there so in this case 4 includes this yes yes yes so this is the entire width that I'll have right just 3 this part 1 this one yeah oh yes you're right it's the same height so I'll include that as well so basically I have a width that is one two three four four and five five minutes and the height would be three so three times five is fifteen so that would be the max area that this particular rectangle would make right so I'll do the same thing for all of these and then I'll keep updating the max the global max as um as I'm going through it but obviously that method will be over N squared time complexity so perhaps is it there's a better way to do it so let's see how we can do it in a better fashion now let's say I am in training through this histogram I start from index 1 so what - what my goal is is that I don't want to iterate through the entire array for every single index I just want to trade through it once and perhaps store some values that I would deem are necessary so let's say I'm starting with the first or the first value or the first index and I see I say that okay the next index or the value of the next index is greater than or equal to itself if it is then I know that I'll be able to expand my rectangle into it yeah right so I'll just keep going till the next value is greater than or equal to myself okay so and then throughout the time let me also record or keep a log because I just want to trade through this array once right I don't want to go back so let me just keep a log of all of the ones that I've already visited so I'll say ok index 0 as I have duplicates over here you know it doesn't really make sense for me to log values so I'll log the indices so I'll say ok I visited index 0 and I'll just keep doing the same thing I'll claim this letter as long as the next value or the next height of the bar is equal to a greater than the current height of the bar so I have 0 1 2 3 four so zero one two three and four right and then when I go to five I know that the height drops so I stop right there because obviously five can't include the three rectangle in its area because this thing is all right right the first bar can't go any further right yes exactly so let me just erase this make it cleaner okay so we are over here right let's let's say we stop right there right and I have this these are the bars that we already encountered on the way so when you stop right here perhaps this is a good opportunity for us to say okay let me just calculate the area that this bar would make yeah so the way we can do it is we can say okay let me start from this point and let me go to the left one unit so that I can cover myself right and I know that the one the bar besides me to the left which is this one it's height is less than myself it may even be equal to myself you know so perhaps in the first iteration you know let's just assume that the bars height is less than myself if that's the case I'll say okay let me just go one unit so this width is one in the height is 5 and my max right now I'm just keep along over here the max area is five now let's say so I don't want to compute anything twice right yeah so I computed the area that this rectangle can make or this this bar can make and I will take that out of my array you know just to say that I'm done with it now I'll say okay let me move further so this bar is done right let me just put a cross over there that bar is done now I move further but I still encounter three that is less than now whatever bar is at the end which is an index three witches a fight for so even for can't extend itself so I apply the same logic as we are over here you know this is the anchor point and we know that all the bars to the right of 4 is out of this alright Ken are the height of them is equal to a greater than 4 right so they can be included in its area so that problems that okay let's start from here and let's go till how far can we go I start over here and then I want to go till whatever is before me right I don't wanna because this is my point so I want to go till whatever bar is before me and get that width and then multiply with my height and I have the area that this bar can make right yeah so let's do that so this is 4 times 2 which is 8 so now this is a new maximum so I update that to it right so now I have the area of this rectangle basically right yeah yeah I'm done with this guy now I'll go further the next one in line that we haven't computed yet so we're done with these two we don't care about those anymore so next one in line that we haven't computed yet is 3 so as I move forward in my iteration I need to make sure the next one is 3 or less than 3 so this one is 3 so it's ok you know I can I can keep stepping up basically in our in our metaphor and I can keep climbing the ladder in my array yes so I can keep in yeah exactly so I can I can include this bar into this bars rectangle right so let me just add that over here and the same thing with the other three so actually this is the index yes is indexed so 0 1 2 3 4 5 5 and then I'll include 6 as well now when I encounter the next one so now I'm done with these two indices right now I'm over here I see that it's going back down this bar can include this one in Syria so I'll anchor myself right there okay I want to stop there and then we'll do exactly the same thing you will say that okay now let's take care of this guy first and see what smack Syria they can make the max area it can make is in this case starting move from the inker going all the way till whatever is before it right because we know that we want to stop at whatever is before it because that can be less than itself yeah so we start over here so this is what 3 times 1/3 it's not greater than max so we we ignore it right at the same time I take this out now I'm over here same thing I can't iterate any further so I need to compute the area of this bar or the the rectangle that this bar can make so same thing my anchor is still over here yeah and I say okay let me go all the way till the rectangle that was before me in this case it's this one so let me just take these two out or the bar yes the bar that was before me so in this case it's a 1 in index 2 which makes total sense right because these two are greater than 3 so obviously this guy will be able to extend into them but as far as our logic goes over here we these are like not even there right we were done with them actually right exactly exactly so everything everything to the left in my record is still less than or equal to the height of my current one so then I say ok let me start here and let me extend this to all the way there right right before my my previous element so then I'm talking about this rectangle here so this is what 1 2 3 4 times 3 which is 12 so I'll update my max right so then I'm done with this guy yeah and I am at 2 now so obviously I can't include this one now right because I can oh sorry it's 3 yes this is not the value so I can't include two yet this is still 3 so I say I do the same thing I started the anchor and I go all the way till the index 1 right and I say okay what is the area over here so this is 1 2 3 4 5 5 times 3 is 18 5 times 3 is 15 so the max will be 15 now right yeah and I'm done with this guy by the way as I'm going through this I'm only concerned with the last index of this array so probably should have used the stack so then put in the implementation I'll actually use a stack and not in the right so so this this guy is done right so now I'm looking at this one so obviously I can include this because this can encompass this in this rectangle so I'll say ok 6 & 7 so these two are done right so let me just erase them and this one's done as well okay so now now I'm done actually now I don't have any more right I can deter it further so I stop right there and then I have some stuff left in the in the array or now it's a stack let's say let me just make it a stack right so I have 1 0 1 & 7 so I say so these are the bars that I have yet to calculate rectangles for right so so I start at index 7 which is this bar I say okay let me calculate the rectangle for that one say okay in order for me to do so I'll need to anchor I'll need to anchor my my my right my right point onto the index after me right it'll probably be at the length and I need to go all the way till this one so I need to stop right there right yeah so I'll have one two three four five six and seven one two one two three four five six yes I'll stop right there so I'll have six six times two is twelve it's still not greater than 15 so it's okay but I'm done with this right now I have one left so the the number index one so I do the same thing I calculate it's rectangle so it's basically from here still the anchor point remains the same all the way till there so this is what six times 2 or 7 times 2 1 2 3 4 5 6 7 7 times 2 that is 14 still less than 15 yeah same thing over here this will be what yeah 1 times 1 times 8 which is 8 so it looks like the max is going to be 15 yeah it looks like this implementation works and also it's just linear time complexity because we're just iterating to this array once and we have stack on the side but we're not really going through all the elements at any given point in time so if you don't mind let me try and transform this logic into into actual code okay so let me erase this erase this as well all right so let's say I have a function let me actually erase this as well let's call it max area and let's say it takes in a histogram so the first thing I would want to instantiate is a stack right so I'll say stack and obviously this is pseudo called stack equals new stack and at the same time I want a global maximum to keep track so I'll say max area actually I already call it max area so let me just call it max our function is max area right yeah max equals zero initially and to iterate through this array as we're anchoring at certain points you know I would use a while loop because I want full control over when I'm incrementing the index and I wanted to be automated so I'll say initial index equals zero and then we'll go into the while loop so I basically say while I is less than hist dot length you should do this now what should we do well if the if the stack is empty then we should push whatever is the index so we shouldn't actually push the values just like I did over here we should push the indices so I'll say if stack dot is empty it's true so is there any other condition when we would push it we would also push the index when it is greater than whatever was index before it right so I would say or if stack dot let's see how would we yeah so if we would say if stack dot peak right so the current index that we have at the top of the stack it should be less than or equal to so it's less than or equal to the value at hist I right yeah so this is the case then we add the element or the index into our stack josè stack dot push high right and we will also say I plus Boston yeah so this concludes this if statement but if this is not the case then as we saw over there what we do is we start computing the area and also we don't just compute the area but we pop it out of the stack right so let's do that else we say let's call it current so at this point the the bar that we are at will be the maximum of all of the bars that we have encountered or of all of the bars that are in the stack right yeah so let's say cur max let's call it car max or her highest you know car max okay let's at Carmack's equal stack dot pop so now I would have popped it so I've I know what its value is right or I can get its value from the histogram all right and then what I do is I would need to compute the area yeah right so at this point I have already incremented I right in the in the previous iteration in the previous iteration I had already incremented I so the way I come here is by checking that hey actually the histogram value at I is greater than my topmost value right so the eye that is the index of Carmack's it will be actually one less than that all right it'll be I minus one so in order for me to compute the area let me just call it area equals I would need the I would I would need the height or basically the value at Carmack's so I'll say hist per max times I would say whatever I is minus one right whatever I is minus one so that would give me the index of this guy right there if this is the current max basically and then I would want to go all the way to my previous number in the stack right so I would say - stack dot peak right so what if if there are no elements in the stack then I would I would just not have this one right I'll just have I minus one so in this case let me actually put that in I would say times stack dot is empty if stack is empty or let me call this if stack is empty then we would say that it should be times I minus one right we don't go all the way but if there is something they will say I minus one - stack dot peak right yeah perfect so now we will have the area and then we'll just do a comparison that if area is greater than max max equals area right yeah so this actually concludes this value so we'll go through all of them at the end we will have some bars left that we haven't computed the the area for so we will have to pop you know all of those so let's do another while loop so we'll say while exactly yeah so I basically say while stack is not empty and I'll keep popping so I'll say while stack dot let's say well stag peak you know well there's something in the stack keep doing this so what do we do we do we actually perform the same logic we will say car max equals stack dot pop right let's say area equals the same computation hist car max times their ternary operator stack that is empty hi - one else hi - one - stack dot peak right yeah and then the same conditional so if area is greater than max max equals area and that concludes a while loop and also includes our function oh yeah we should also return the my next value at the end we didn't do all this work for nothing so I'll say it in return max thanks for watching guys if you like this video let me know by hitting like button below and next week I'm actually giving you the option of choosing which problem I should cover so the first one is should I cover n Queens where you need to place n Queens or n number of Queens on a chessboard such that none of the Queen's are attacking each other or the second one is 0-1 knapsack it's actually a very popular problem with dynamic programming so let me know in the comments below which one you would like me to cover and I'll see you next week

Channel: Irfan Baqui

Views: 99,178

Rating: 4.4815226 out of 5

Keywords: maximum histogram area, maximum rectangle area in histogram, maximum histogram, max histogram, maximum histogram using stack, largest rectangle, largest rectangle in histogram, largest rectangular area in a histogram, maximum rectangular area in histogram, maximum area of a rectangle, coding, stacks, coding interview, coding interview question, coding interview question and answer

Id: RVIh0snn4Qc

Length: 24min 28sec (1468 seconds)

Published: Thu Jan 25 2018