Largest rectangles in histogram

Question

I'm working on the below algorithm puzzle and here is the detailed problem statement.

Find the largest rectangle of the histogram; for example, given histogram = [2,1,5,6,2,3], the algorithm should return 10.

I am working on the below version of code. My question is, I think i-nextTop-1 could be replaced by i-top, but in some test cases (e.g. [2,1,2]), they have different results (i-nextTop-1 always produces the correct results). I think logically they should be the same, and wondering in what situations i-nextTop-1 is not equal to i-top

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        height.push_back(0);
        int result=0;
        stack<int> indexStack;
        for(int i=0;i<height.size();i++){
            while(!indexStack.empty()&&height[i]<height[indexStack.top()]){
                int top=indexStack.top();
                indexStack.pop(); 
                int nextTop=indexStack.size()==0?-1:indexStack.top();
                result=max((i-nextTop-1)*height[top],result);
            }
            indexStack.push(i);
        }
        return result;
    }
};

Answer 1

The situations where i-nextTop-1 != i-top occur are when the following is true:

nextTop != top-1

This can be seen by simply rearranging terms in the inequality i-nextTop-1 != i-top.

The key to understanding when this occurs lies in the following line within your code, in which you define the value of nextTop:

int nextTop = indexStack.size() == 0 ? -1 : indexStack.top();

Here, you are saying that if indexStack is empty (following the pop() on the previous line of code), then set nextTop to -1; otherwise set nextTop to the current indexStack.top().

So the only times when nextTop == top-1 are when

1. indexStack is empty and top == 0, or
2. indexStack.top() == top - 1.

In those cases, the two methods will always agree. In all other situations, they will not agree, and will produce different results.

You can see what is happening by printing the values of i, nextTop, (i - top), (i - nextTop - 1), and result for each iteration at the bottom of the while loop. The vector {5, 4, 3, 2, 1} works fine, but { 1, 2, 3, 4, 5} does not, when replacing i-nextTop-1 with i-top.

Theory of the Algorithm

The outer for loop iterates through the histogram elements one at a time. Elements are pushed onto the stack from left to right, and upon entry to the while loop the top of stack contains the element just prior to (or just to the left of) the current element. (This is because the current element is pushed onto the stack at the bottom of the for loop, right before looping back to the top.)

An element is popped off the stack within the while loop, when the algorithm has determined that the best possible solution that includes that element has already been considered.

The inner while loop will keep iterating as long as height[i] < height[indexStack.top()], that is, as long as the the height of the current element is less than the height of the element on the top of the stack.

At the start of each iteration of the while loop, the elements on the stack represent all of the contiguous elements to the immediate left of the current element, that are larger than the current element.

This allows the algorithm to calculate the area of the largest rectangle to the left of and including the current element. This calculation is done in the following two lines of code:

int nextTop = indexStack.size() == 0 ? -1 : indexStack.top();
result = max((i - nextTop - 1) * height[top], result);

Variable i is the index of the current histogram element, and represents the rightmost edge of the rectangle being currently calculated.

Variable nextTop represents the index of the leftmost edge of the rectangle.

The expression (i - nextTop - 1) represents the horizontal width of the rectangle. height[top] is the vertical height of the rectangle, so the result is the product of these two terms.

Each new result is the larger of the new calculation and the previous value for result.