Coding Interview Problem: Largest Rectangle in a Histogram

what up this is Jackson Gabbard back for episode 5 of the unqualified engineer I'm going to be real with you people getting a little bit bored with the polite PC delicate episodes that I've been up to recently I'd like to just keep it a little bit more real with you all and so this episode you're gonna get the raw uncut Jackson and that has nothing to do with my parents decisions related to my Anatomy when I was a baby I mean I just want this to be more authentic me coming out and so brace yourselves because I might use some wordy dares got some new markers for my glass very nice best part is when you spray them it looks like blood so for this episode we're going to be exploring an oldie but a goodie the largest rectangle within a histogram problem and while this problem is not super algorithmically complex the optimal solution to it is more surprising than you might expect and drawing straight lines is hard let me try again oh no it so what do we mean when we say a histogram this is something that everybody even knows about I guess a histogram basically is an X and a y-axis where for every X you have some Y value and for this problem we're going to assume that all of those Y values are positive integers and the goal here is to try to figure out if you have a histogram what the biggest rectangle you could draw with in it would be so you know from the far left side to the far right side where in that histogram is there the biggest rectangle and now if you look at my example here it's pretty obvious straight away that the big tall six by six by two rectangle is the biggest rectangle that gives you an area of 12 so that's the obvious case but there are lots of other cases that are not obvious at all for instance what if we modify the histogram to look like this so you can see now we've got some real contenders for the largest rectangle case we've got a three by two we've got a three by three but then you'll notice way down here at the bottom we actually have a two by seven which is in fact the largest rectangle in this histogram let's get to the exciting part let's talk about the algorithm for this to brute-force this algorithm you would basically start at every X position and go up through the y-axis of that X and go to the right until you hit something that doesn't fit and then keep that maximum area you've seen across each position in the x axis and that would kind of get you there that would definitely eventually get you to a correct answer but you would do so much work so much unnecessary work because you would in fact spend a ton of your time just recounting the positions in the histogram that you've already seen before so a much better option is one that doesn't require you to do any backtracking or to recount any of the squares in the histogram again and again and again and the best solution to this that I know uses a stack and the algorithm for it is pretty cool actually the idea basically is that any time you reach a new height in the histogram going from the left to the right you could be starting a new rectangle you can't no in fact you won't know until you hit a lower height until that until you've reached the terminal point and whatever that rectangle might be and so the algorithm for this works pretty much that way you start from the left side you check to see if here at the first or at the biggest height you've seen so far and if you are at that position then you push it into a stack now we actually need two stacks we need one to store the height and one to store the position and we'll make sure they stay in sync so if we look at this example as soon as we hit the first one we know that we might have a rectangle of height one but we don't know how wide it might be so we'll just push that into our stack we'll keep track of that and then we'll move on to the three now if we're in the three we still have the one going because three is bigger than one but we also might have a new rectangle starting of height three and in fact we know we have at least a one by three because that's the definition of the histogram so we'll push three into our stack as well and we'll keep going now when you get to the two two is smaller than three so we know that our height three rectangle is done it can't be any wider than it is because there's literally no more histogram with three in it so at this point we need to get rid of our three but we need to keep track of it because it might be the biggest one at least we don't know that it's not yet but we should be really clear about how we're deciding the size of the rectangle that we've seen now visually it's obvious that it's a high three and with one rectangle but we have to think in the general case here the general case is basically saying we know because of the contents of the stack the we have at one point seen the height three and it was at some position now in this case the position is at position one but we're now at position two and so the only way to know the height and the width of this rectangle is to say what was the height that we saw and then where are we now - where did that rectangle start so if we're at - right now if we subtract the one from it that gives us one and three times one is three which is the correct size or this rectangle and so knowing that knowing that we have seen a size three rectangle we can keep going that's that's as much information as we need because that gives us enough information to either return this three if it is in fact the biggest rectangle or to discard it if we find a bigger one later now let's talk about how we would proceed forward we want to keep leveraging this stack to make sense of the problem so now we've got two and the immediate question we have to ask is what's on top of our stack we don't have a bigger value than two on the stack and so we need to push two onto the stack so there's actually a kind of a subtle thing here which is that the two doesn't start with itself the two actually started inside the three and so while we'll store the height two in the stack for the heights we don't want to store position two we want to keep position one because that's actually where our rectangle started and so we'll proceed forward from there with the same process and in this case the very next thing we hit is a height one at position three we're going to take everything off of the stack that's taller than height one and we're going to figure out what size rectangle those taller Heights were composing and then figure out if those rectangles are bigger than the biggest rectangle we've seen and that's how we're going to find the biggest overall rectangle so we take our two and then we take the position that it started which was position one and we say okay so two is our height where are we now now we're at position three this started at position 1 so 2 times 3 minus 1 gives us 4 and so now all we need to do is choose the maximum value between what we've seen before and what we have now and if we keep doing that we will always keep the biggest value there no matter if it was earlier in the histogram or later in the histogram and now we've done our first real replacement of the biggest tangle at first we thought it was the height three with one rectangle but now we've got a two by two that's bigger it's a bigger area and that's awesome so and so we return to our stack with our current position and the value we have at our current position is 1 well it turns out one is already in the stack and so we don't need to replace it we can just keep on rolling so when we reach the next point in the histogram we find that we've got 2 now 2 is bigger than our one and so we're going to push another position onto our stack we'll put the 2 into the height stack and the 4 into the position stack and so now we're out of histogram we've reached the end the only thing we have left to do is to digest what's in our stack as we reach the end of the histogram we need to tally up the size of the rectangles that we've been keeping track of that we haven't reached the end up yet and in this case we have two rectangles that have been open but not shut so to speak now this height to start a deposition for we're now sort of at position 5 which is to say we're at the width of the histogram and so if this started a position 4 we're going to subtract 4 from 5 we get 1 2 times 1 is 2 so this is just a 2 by 1 rectangle not interesting well ditch that but then what about this one what about this height 1 rectangle well it started way back at position 0 way back in the day and we've been carrying it along since we first started this problem so let's do the math on this the position is 0 and if we're considering the full width of the histogram is 5 5 minus 0 is 5 so 1 times 5 means that we actually have found our biggest rectangle and this biggest rectangle is a 1 by 5 area 5 rectangle which is clearly bigger than the 2 by 2 that we found before and if you're seeing this thinking what is even talking about like what height 1 rectangle are you talking about let me color it in now you see that fancy wonderful height 1 rectangle that's been lurking there the whole time just waiting for you to notice it all that wanted was your love and you kept it at the bottom of the stack you animal so today we're going to code in Java just kidding we're coding in JavaScript I like most people who code in Java don't know Java now since we're writing in JavaScript we need to carefully consider all both of the available data structures we got the object and we've got the array it would be awesome to have a real stack data structure that we can use for this because it's much more memory efficient and the API that it offers is the correct API for stack operations but this is JavaScript so we'll put away our dreams of memory efficiency with our hope to have a coherent substring API and then we don't have a histogram class either we can just leverage of Anila javascript array because javascript only has two data structures they're both super versatile they have almost as many uses as jquery has overloaded function signatures so we'll represent our histogram as a javascript array within with a positive integer and every position that will represent the y-axis and then the position in the array will represent the x-axis so let's call this function find largest rectangle so right off the bat I can know that we need at least something to address the height that were currently at and something to store the position that we're currently at so today we're going to code using a for loop which is an ancient form of loop used way before there was a for each for everything back before javascript engineers only knew how to do things with callbacks javascript is just so full of callbacks unlike my dating life so we can use an object or we can use an array to represent our stack I think it probably makes most sense to use an array for efficiency's sake you really want to avoid manipulating the data structures pushing popping things like that luckily v8 is done a pretty good job of optimizing the basic array operations like push and pop so even though we're abusing the data structure I think it will be fairly efficient so instead of using a peek method like you would in a normal stack we'll just index to length minus 1 so remember we have two cases here basically we've got the case where we are either at the beginning of our stack or we have a value that's bigger than what's on top of our stack and in that case we just want to push these values this height in this position into their respective stacks and then there's the other case the case where whatever we've arrived at is less than what's on the top of our stack if we're there then we got to do some real work if you remember back a few minutes where we discussed the algorithm for this what we said was when you find a height that is smaller than the height that's on top of the stack you have to pop that item off the stack figure out what size rectangle it was composing figure out if that was the maximum size of rectangle you've ever seen here I'm going to do something a bit creative I am going to take advantage of JavaScript's ability to just put functions anywhere because after all javascript scoping is looser than the Taco Bell shits so my function within a function is called pop that because we're going to pop that off the top of the stack as many times as it takes to get to a height that is the same or lower than the height that we currently have they I have a very specific reason for doing this I'm going to use exactly the same logic in a couple of places in my trial runs I actually ran out of whiteboard space so I'm going to move pop that up here to the right corner to keep it out of the way so just imagine that pop that is declared as a function inside of this function right here and the logic of pop that is actually pretty simple we need to know the height that's at the top of the stack we need to know the position that's at the top of the position stack and because we have access to the enclosing scope we can also know what the current position is and if you remember back to our walk through the algorithm those three things are what you need to determine the area of whatever rectangle we're currently closing and take note I'm not creating the variables that pop that is interacting with inside of the scope pop that I'm creating these variables in the enclosing scope and that's because I want to have one scope where all of my variables exist because as you'll see in a second I actually need some of the results of pop that inside the fine largest rectangle function so really just think of pop that as a four line helper that is completely subordinate to the fine or just rectangle function and once we grab the height and the position that's at the top of the stack we're going to calculate the area of the rectangle that we just finished that we just popped off the stack and we're going to figure out if that area is bigger than the biggest area we've seen that's all pop that is four so after some number of poppings we will have reached a position in the stack where the current height in the stack is less than the height that we care about the height that we're currently at and if that's at the beginning of the list where all the way at the start of the stack you're going to put that back onto the top of the stack so that you don't lose track of where the current rectangle that you're dealing with started and remember to be in the state that we're in at all there had to have been bigger values in the left-hand side of the rectangle that are just now coming to a close with our current value which means whatever value we have right now the rectangle that it's composing actually started somewhere to the left so we need to keep tract of that temporary position that sort of earlier position value and push back onto the stack with the height that we're currently at and where that height started another way to think about this process is sort of looking back in time let's say we're at a height - and we've got three things on the stack already then two is now the smallest number that means that this - actually started three positions ago and so we need to go back in time and figure out what the first value in the stack is that's bigger than two and steel its position because that's actually the start point of our height - rectangle so once we've finished iterating over this list we might have a bunch of stuff in the stack that hasn't closed yet that hasn't had a lower value come next and so basically we need to redo the pop that approach but instead of stopping when we hit a smaller number we're going to stop when we hit the end of the stack when the stack is empty we don't yet know what the areas of those rectangles might be so we actually have to do another loop here to purge the stacks to grab each value out of them and calculate the area of the rectangles that they represent and from those figure out what the maximum value would be and with that you can pretty much just mark a drop and walk away because you are the Supreme Lord of code all kneel before me and my insane algorithmic competence but if you did that you'd be up because the first thing you should do when you finish coding an algorithm like this is look at your own code line by line and look at what you up because you did something up so here for instance if we take a step back you'll notice for one I didn't close the array access for Shane Gabbard for shame and so then you can mark a drop in flexed oh I'm the king of all the code ah but if you did that you would still be up because in fact there's a glaring error in this code and it's in the second half of the if-else the mistake here is the assumption that the stack has to be empty in order to push the value back on top of it and you can see the error of this if you imagine a histogram of the sort of 1 3 2 in that case when you get to the two you will have a 1 and a 3 on the stack already now if you pop the 3 off because you should because that's what the algorithm will do then there will still be a 1 in the stack so the length of the stack the height of the stack is going to be 1 but you still need to push that 2 back in there so this is actually incorrect logic we're just going to kind of magically wipe that out and with that you can declare everyone your royal subject and tell them to kiss the ring that's the American ring not the British ring I hope you enjoyed this episode this is number five of the series and it's going to be the last one for a few weeks because I'm getting ready to move as always if you liked the episode if you hate the episode if you think my JavaScript sucks I mean let's be real it sucks then hit me up in the comments let me know what you think and if there's a specific question you would like to see here also comment with that as always thanks for watching blood

Channel: Jackson Gabbard

Views: 284,032

Rating: 4.4782171 out of 5

Keywords: code, coding interview, javascript, algorithm, facebook interview, google interview, histogram, rectangle, whiteboard

Id: VNbkzsnllsU

Length: 16min 18sec (978 seconds)

Published: Thu Jun 02 2016

Reddit Comments

[u/[deleted]]

As someone in the learning stages, thank you for doing this.

[u/williamshoops96]

This is cool man, definitely a very useful series and I've subbed!

[u/taggzor]

Cool, thank you!

[u/ssfcultra]

Nice intro, motherfucker. Watched a bit. Great explanation. I like the visual style. Going to watch the rest tomorrow.