Largest Rectangle in Histogram

I was working on a LeetCode problem a few days ago.  I was able to come up with a brute force solution, but wasn’t able to get any further past that.  On the discussion board a user gave a solution that utilized histograms.  The user also referenced another problem for more histogram practice.  I don’t know about you, but I could use some more histogram practice.  Let’s figure out how to solve “Largest Rectangle in Histogram”.

The Problem

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example

Example 1:
Input:  heights = [2, 1, 5, 6, 2, 3]
Output:  10

Example 2:
Input:  heights = [2, 4]
Output:  4

Link to Problem

Brute Force

Understand what we are trying to find?  We want to find the largest possible rectangular area that can exist within the histogram that is pictured above.  The rectangle can span across multiple columns, but it has to be only one rectangle.

The best way to get some ideas on how to go about optimally solving the problem is to first look at the brute force solution.

Here is the code for the brute force solution: 

The time complexity of this algorithm is O(n ²) with n = heights.length.  The space complexity is O(1); no extra space is used. 

Let’s take a look at some illustrations that show what one full iteration of i looks like.

What did you notice in the illustrations?  A lot of unnecessary work right?  At first when both i and j = 0, the minimum height is 2.  After that though, the minimum height is 1 for the rest of the time.  It seems rather unnecessary to have to calculate a new area every single time that j increments.  Wouldn’t it be much better to only ONCE have to find the maximum area that exists for each of the different column heights?

Still not sure what I mean?  Ok let me try to explain it a bit more.  The column height of 1 is the absolute minimum of the column heights.  Every column in this histogram has a height of at least 1.  Thus, the maximum width that corresponds to the column height of 1 is 6.  6 is the total width of the histogram.

On a side note, I have found that it is good practice to start sentences with words like “Thus”, “Conclusively”, and “Unequivocally”.  It is a good way to let people know that you are wicked smaht and an even better way to lose friends quickly.

Ok back to business.  Let’s look at some more maximum areas that correspond to a specific column height.   

The picture above corresponds to the column height of 2.  What do you notice about it?  It stops when it hits the column height of 1.  The column with the height of 1 creates a bound for our rectangle.  1 is less than 2 and because 1 is less than 2, it creates a boundary.

One more illustration.

This area corresponds to a column height of 5.  6 is greater than 5, so we are able to extend our rectangle into this column.  However, 2 is less than 5, so it creates a boundary.  Likewise, 1 is less than 5, so it too creates a boundary.

Do you get it now?  For every individual column there exists ONE maximum rectangular area that corresponds to that current column’s height.  That rectangle is able to extend into the neighboring columns as long as that column has equal to or greater height than the current column’s height.

This is what the optimal algorithm needs to do.  It needs to iterate through each of the columns and ONLY calculate the area if it is going to be the maximum area that corresponds to that particular column’s height.  It then needs to return the absolute maximum area from all of these local maximum areas.

How do we do this?

How to Solve

When I was trying to solve this problem, I kept thinking to myself that I needed to use a stack.  I had a very strong hunch that it could be solved with an approach similar to the one used in this problem.

The only problem was that I just couldn’t figure out how to get it started.  Sure enough, when I went to check on the discussion board, there was the solution that I was trying to get to.  That solution uses a stack.

Here is how it works:

1. Look at the height for a column.
2. If the height is greater than or equal to the first height at the top of the stack or if the stack is empty, push the height onto the stack.
3. Otherwise pop from the stack.  The maximum rectangular area that exists for this popped height is then calculated.
4. Continue to pop until the top stack height is less than the column height from step 1.

Some really important things to note about this algorithm.  I mentioned earlier that the rectangle is able to extend into the neighboring columns only if they are equal to or greater than in height.  This is what our stack is going to facilitate for us.  As soon as a column is reached that is shorter than the column at the top of the stack, the column at the top of the stack is popped and its maximum area is calculated.  The stack creates that boundary for us.

Think about it.  Let’s say column B in the stack is positioned right below column A in the stack, but there is also column C that is right below column B.  The means that the rectangular area for column B can extend into column A, but it cannot extend into column C.  The stack is sorted by height.  The lesser heights will always be at the bottom and the greater heights will always be at the top.

The Code

Here is some real top-notch code submitted by LeetCode user @legendaryengineer.  You can find the original post here.

Some Illustrations

Let’s take a look at some illustrations to really give us a crystal clear mental picture of what is happening with this algorithm.

Figure A shows the initial setup.  The stack is empty, so push i = 0 on to the stack.

In Figure B, h = 1 and 1 < 2.  The column that has a height of 2 is popped from the stack and its max value (2 x 1) is calculated.  The stack is empty.

In Figure C, i still equals 1 and the stack is empty.  Push i onto the stack.

In Figure D, i = 2.  The height associated at i = 2 is greater than the height associated with i = 1.  Push i = 2 onto the stack.

In Figure E, the height associated with i = 3 is greater than the height associated with i = 2.  Push i = 3 onto the stack.

Spoiler alert, there is going to be a pop in the next step.  Let’s take a look at our stack really quick.  If you notice, it is sorted by height.  1 is the minimum height.  6 is the maximum height.  

This is what is going to happen in the next step:  i = 3 will be popped, and because the stack is sorted, we know that it will not be possible for a rectangle that has a height of 6 to extend into the column that has a height of 5.  Also because i = 3 is being popped in the first place, we know that it is not possible for a height of 6 to extend into the neighboring column to the right, either.  The maximum area for i = 3 will be 6 x 1 = 6.

In Figure F, the height that corresponds to i = 4 is less than the height at the top of the stack.  Pop the top, find the maximum area (6 x 1) that corresponds to the popped height, and stay at i = 4 until the height at the top of the stack is less than the height that corresponds to i = 4.

In Figure G, the height that corresponds to i = 4 is less than the height at the top of the stack.  Pop the top, find the maximum area (5 x 2) that corresponds to the popped height, and stay at i = 4 until the height at the top of the stack is less than the height that corresponds to i = 4.

In Figure H, the height at the top of the stack is less than the height that corresponds to i = 4, so i = 4 can finally be pushed to the top of the stack.  i is incremented.

In Figure I, the height at the top of the stack is less than the height that corresponds to i = 5, so i = 5 can be pushed to the top of the stack.  i is incremented. 

Figure J shows that i = len.  This is going to cause everything in the stack to be popped off and each of the maximum areas to be calculated.  The maximum area here is 3 x 1 = 3.

Figure K shows the maximum area being calculated for i = 4.  It is 2 x 4 = 8.  Now the stack is empty.

Figure L shows the maximum area (1 x 6) being calculated for i = 1.  When the stack is empty the width that is multiplied by the height is i.    Just a reminder that i = 6 right now. 

The width can be i at this point, because if the stack is empty there cannot exist a neighboring column to the left of i = 1 that has a greater height than the height at i = 1.

Figure M shows that the stack is empty.  Push i = 6 on to the stack.  This value of i exceeds the conditions of the for loop.  The algorithm is finished.

maxArea = 10

Time Complexity

If n is the number of elements in heights[] then n + 1 is iterated through in the for loop.  This gives O(n + 1).  A total of n elements are popped from the stack, so now it’s O(2n + 1).  The constant is dropped and only the dominant term is considered.  The time complexity is asymptotically equivalent to O(n).

Space Complexity

The space complexity will be O(n) as well.  The height of the stack will never exceed the length of heights[].

Learn some more Big-O tips and tricks.

Get Better at Algorithms!

Algorithms and data structures are pretty tough.  They are definitely taking a while for me to get the hang of them.  However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me.  If I missed any that have been helpful to you, be sure to mention them in the comments.

• Cracking the Coding Interview – Great resource.  Really gets you in the right mindset for interviews.  You can find it here.
• Elements of Programming Interviews – Another great book.  Personally, I like this one more than CTCI, but YMMV.  You can find it here.
• Grokking the Coding Interview – Can’t emphasize this one enough.  Haven’t seen it mentioned it too often.  Explains patterns that occur in different coding challenge problems.  Great at providing a big-picture of all the different algorithm problems you might encounter.  Check it out here.
• Grokking Dynamic Programming – Dynamic programming is tough.  This course has definitely helped me get a better understanding.
• Tushar Roy – Tushar really knows his stuff.  His dynamic programming playlist is especially good.  Check out his awesome YouTube channel.
• Back To Back SWE – Great YouTube Channel.  Highly recommend.
• Kevin Naughton Jr. – Another awesome YouTube channel.  Great at going over problems and gives helpful advice.
• Base CS – Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures.  Check out the blog series here.  She also has a podcast that I give two thumbs up.
• Coding Challenge Website – There are plenty of different ones to choose from.  HackerRank, CodeWars, and Edabit all seem to be pretty popular.  I personally use LeetCode.  Find the one that works for you!
• Pramp – Do mock interviews!  The sooner the better!  Pramp has been a huge help to me.

Well, I hope that was useful.  Thanks for reading my post and best of luck with your learning about data structures and algorithms!