Leetcode: Largest Rectangle in Histogram

 This question is asked at Amazon, Microsoft, and Adobe. 

Given an array of integers heights representing a histogram's bar height where the width of each bar is 1, return the area of the largest rectangle of the histogram. 

Here's an example: 

We are given an array with the histogram, and we want to figure out the area of the largest rectangle formed. Let's assume the example is [2, 1, 5, 6, 2, 3] and the largest rectangle is between the 5 and 6.  We need to find all of the areas, so we should return the maximum area. 

From this, we can observe that at least 1  bar is fully included in the largest rectangle.

If we can find the areas of all the largest rectangles for each bar/s included in full, we can find the maximum rectangle area. 

First, we will for all the rectangle for at least 1 bar in full.

So here are the steps:

1. find the largest rectangle including each bar one by one.

2. Take the maximum value of all the maximum areas of each bar found.

The second step is pretty good, but the first step needs more observation. We have to have the nearest left bar with a height less than a current bar and the nearest right bar with a height less than the current bar. Else, we do this for 0.  The width is the rightmost bar - leftmost bar + 1. For each bar, we want to find the leftmost limit as well as the rightmost limit. We use a stack to keep track of the previous smaller bars. We maintain the elements in increasing order with the largest bar being at the top of the stack. The stack contains elements with height less than the left hand side of a bar. We get the values and indices and then figure out the final values. The stack wi ll keep track of the maximum area which reduces the traversal to O(N). 

Here is the following issue in C++:

class Solution {

    public: 

        int n = heights.size();

        vector<int> left(n), right(n);

        stack<int> mystack;

        /*

        if the stack is empty, just push the next index inside of the stack 

        */

        for(int i = 0; i < n; i++) {

            if(mystack.empty()) {

                left[i] = 0;

                mystack.push(i);

            }  else {

                /*

                if stack isn't empty and the height of next element is greater pop the element on the stack

                */

                while(!mystack.empty() and height[mystack.top()] >= heights[i]) {

                    mystack.pop();

                }        

                /* 

                now we find the leftmost index and keep pushing

                */

                left[i] = mystack.empty() ? 0 : mystack.top() + 1;

                mystack.push(i);

            }

        } 

        /*

        Pop the stack and solve the rightmost problem.

        */

        while(!mystack.empty()) {

            mystack.pop();

        }

        for(int i = n - 1; i >= 0; --i) {

            if(mystack.empty()) {

                right[i] = n - 1;

                mystack.push(i);

            }else {

                /*

                If the stack is not impty and the height is greater then pop the stack

                */

                while(!mystack.empty() and heights[mystack.top()] >= heights[i]) {

                    mystack.pop();

                }

                /*

                then if the rightmost stack height is lower, mark this as the right mark and push 

                the element in the stack.

                */ 

                right[i] = mystack.empty() ? n-1 : mystack.top() - 1;

                mystack.push(i);

            }

        }

        int mx_area = 0;

        /*

         Calculate the maximum area out of all of the multiplications 

        */

        for(int i = 0; i < n; i++) {

            mx_area = max(mx_area, heights[i] * (right[i] - left[i] + 1));

        }

        return mx_area;

}