Largest Rectangle in Histogram
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.
The problem is very well known, here I will try to present my point of view for approaching the problem and solving the problem in the easiest way possible!
So, the concept is we will consider every bar as a minimum height bar and try to calculate the rectangle by considering that current minimum height as the right boundary for its previous bars of larger heights.
There is a great chance of misconception or wrong intuition about the fact that we are considering every bar as minimum height and calculating area possible by including that height in it with other bars to its left→ IT IS WRONG!!
Instead we fix a min bar and try to figure out all possible bars of greater height to its left till this as right boundary. (GREATLY ILLUSTRATED IN DIAGRAMS).
Another scope for misconception can be that we are calculating area considering bars from left to right → THIS IS AGAIN WRONG!!!
Instead we are calculating from left to right, considering current bar as right boundary, NOT INCLUDING IT. We go to the left until and unless the bar height becomes less than the right boundary bar’s height.
So, for that reason we will be using stack to store the elements and facilitate the continuous comparison property which is core for this algorithm, where we constantly compare consecutive elements in the input stream, and that’s why STACK is the Chosen one here!!
(IMP → WE WILL BE PUSHING THE INIDICES, NOT THE ACTUAL HEIGHTS, COZ EVEN IF SOME BAR IS POPPED, BUT STILL, WE ACTUALLY WANT TO MEASURE THE DISTANCE FOR WIDTH CALCULATION).
The formula to calculate is rectangle area is → height*width →
height*(right-left-1)
Then we have our stack as →
Now we can insert bars as they are having increasing height →
Now we have encountered 2, which is less than stack top.
So as per algorithm, we will keep popping out larger values than current bar height 2.
And in this way, we will gradually step by step calculating rectangles from left to right.
With a right boundary fixed at current height of height 2’s position.
And left boundary changing through left until we encounter a value less than the Current considered right boundary value’s height.
curr_area=6*(4–2–1)=6
This is current encountered histogram bar (shown with blue color not pushed onto stack until and unless, stack top becomes less than it).
Now popping out 6 and taking height 5 as min height and left of 5 as left boundary and we already have a fixed right boundary!! This calculation is valid, as we only push to stack if the values are increasing, so going from right to left ensures that we are sure to get same or more than curr height to the right of curr , till we see any smaller height.
So here it does not matter as we have already popped
Out 6, as we know , we are sure to get a min height of 5
To the right of 5(because it was inserted top of 5 only
Because the height is more or equal to 5)
This is current encountered histogram bar (shown with blue color not pushed onto stack until and unless, stack top becomes less than it).
Now the stack looks like →
This is current encountered histogram bar (shown with blue color not pushed onto stack until and unless, stack top becomes less than it).
Then after 3 come as 3 is bigger than stack top , so it gets pushed to stack →
NOW very important point, if you go through the algorithm we have at the very 1st step added a sentinel value to the end of the given heights vector, so to pacify this current scenario -
As u can see in this case there are items left in the stack, so some more area calculation is left,
We had to do it by running another while loop separately otherwise,
By adding a 0 at the end of the height vector, we are unifying the logic for every case➔
As we know whenever we encounter a smaller value than the stack top, we will keep popping out until we get a smaller value at stack top.
And we know that the smallest height possible is 0, so we are keeping a sentinel added as 0 height, thus ensuring that we are popping out and calculating all possible rectangle areas with smaller heights as well (as no height can be smaller than 0).
And now the area calculation looks like the flow →
curr_area=3*(6–4–1)=3
curr_area=2*(6–1–1)= 8
curr_area=1* (6-(-1)-1)=6
The dashed boxes show popped out bars, they are still there just to provide that min height of left bar (discussed previously).
The code looks like →
class Solution {
public:
int largestRectangleArea(vector<int>& heights)
{
int max_area = 0;
stack<int> stk;
//adding a guard 0 height bar to maintain integrity such that
//if there is any bar left for calculation it would be calculated //by considering 0 as a min bar for right boundary(as it can be the min bar height possible) thus ensuring every remaining rectangle calulations.
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
while(!stk.empty() && heights[stk.top()] >= heights[i]){
int h = heights[stk.top()];
stk.pop();
int l = stk.size() > 0 ? stk.top() : -1;
int area = h * (i - l - 1);
max_area = max(max_area, area);
}
stk.push(i);
}
return max_area;
}
}If you want to practice → https://leetcode.com/problems/largest-rectangle-in-histogram/
🤞🤞Happy Coding 🤞🤞
