Daily bit(e) of C++ | Maximum rectangle in a histogram
Daily bit(e) of C++ #217, Common interview problem: Maximum rectangle in a histogram.
Today we will look at a common C++ interview problem: Maximum rectangle in a histogram.
Given a histogram as std::vector<int>, where each element represents the height of the bar at index i.
Determine the size of the largest rectangle that can be drawn inside the histogram.
For example, for the input {1, 5, 4, 1, 4}, the maximum rectangle is of size eight, spanning the elements {5, 4}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/jf31TGj5E.
Solution
Let’s first consider a simple scenario when the values in the histogram are strictly increasing. In such case, we have n potential rectangles, one for each unique height. Each of the rectangles is bounded by the element to the left and the end of the histogram on the right.
If we add in equivalent values, making the histogram monotonic, we can still apply the same logic; however, now we want to only consider the last element with each unique value (because this element will create the left bound for the next higher value).
Finally, let’s consider the case when we have three consecutive elements with values A, B, and C, where A < B && B > C. In this case, the rectangle with height B is bounded by the positions of elements A and C.
This very strongly points to the monotonic stack data structure. We can scan the histogram from left to right, applying the following logic:
If the current element has the same value as the top of the stack, remove the top. Add the current element to the stack as the new left bound for the next higher value.
If the current element is lower than the top of the stack, it creates a right boundary for some of the elements on the stack. We must process all such elements to restore the stack to a strictly increasing state.
If the current element is higher than the top of the stack, we add it to the stack.
In the end, we are left with a strictly increasing sequence of elements in our stack, or more appropriately, from the perspective of removing elements from the stack, a strictly decreasing sequence. We can then process the elements; each is bounded by the next element on the stack and the right border of the histogram.
Because each element is only added and removed from the stack once, we end up with O(n) time and space complexity.