Largest rectangle in a histogram - PrismoSkills

Largest rectangle in a histogram - PrismoSkills
Problem: Given an array of bar-heights in a histogram, find the rectangle with largest area.
Solution:
Assuming, all elements in the array are positive non-zero elements, a quick solution is to look for the minimum element h_min in the array.
Then numElements * h_min can be one of the possible candidates for the largest area rectangle.

If that is not the largest rectangle, then the solution for the largest rectangle will not contain h_min bar.
hmin = findMinimum (start, end, arr);

maxAreaRectangle = max (
    hmin * (end-start),
    maxAreaRectangle (start, (hmin -1)),
    maxAreaRectangle ((1+ hmin), end),
);
An O(n) solution can be found as follows:

For any bar in the histogram, bounds of the largest rectangle enclosing it are those bars which are smaller than the current bar.
This means that the largest rectangle enclosing any bar will have bars greater than or equal to that bar.

Hence whenever we see two consecutive bars such that l_k < l_k-1, we know that the rectangle for l_k-1 must end there itself.
So any l_k < l_k-1 property tells us the right bound for rectangle of l_k-1.

Exploiting this property, following algorithm can be used:

1. Loop over the input array and maintain a stack of increasing bar lengths. This can be called an Increasing Stack
2. If current element is greater than stack-top, push it to stack top.
3. If current element is smaller than stack-top, then start removing elements from stack till it has elements greater than the current.
   For each popped element, find largest histogram area using:
   
   1. Right boundary as current element or current element - 1 (as explained above)
   2. Left boundary as next stack-top element or 0 (Because our stack stores only increasing length of bars, it implies that all bars absent between two consecutive bars in the stack must be longer than both of them)
   3. If all elements of the stack have been popped, this means that all bars before the current bar were longer and so their rectangles ended here. To begin afresh for the others, current bar is put into the stack.
4. If any elements are left in stack after the above loop, then pop them one by one and repeat #3

Read full article from Largest rectangle in a histogram - PrismoSkills