Leetcode 84: Largest Rectangle in Histogram

An O(n²) solution is simple but fails time limit on a leetcode test case. The O(n²) solution goes through each element and for each one it finds the next smallest to the left and next smallest to the right. That box will determine the maximum area for that bar.

An O(n) solution involving a stack exists and although the solution is very concise, it is somewhat unintuitive and difficult to follow. It follows similar principle to the O(n²) solution, but we push elements to a stack if they are bigger than previous to deal with them later. As we move through the bars, we are looking for the end of an area box, which is marked when a bar (i) is smaller than that previous bar on the top of the stack. We stop to deal with that top stack bar, so pop it and call it’s index tp. We then go back to the stack (s) to find out the starting bound of the area box, which is marked by the next item in the stack, which is smaller than tp. We calculate the area = heights[tp] * (i – s.top() – 1); unless there is no item in the stack in which case area = heights * i; i.e. span all the way to the beginning.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.