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

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an 
area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 10^5

• 0 <= heights[i] <= 10^4

Intuition

Need to maximize the area formed by a rectangle by combining rectangles from left and right.

If the heights of the rectangles on the left/right sides are more than or equal to the length of the current rectangle we can combine those to calculate the area and the resultant area will be the height of the current rect * width.

Width can be calculated by the distance between the indices of the chosen rightmost and the leftmost rect which is the nearest smaller to the current one.

Approach

• To choose the leftmost rect we can find the nearest smaller left and similarly nearest smaller right using the stack in O(N).

• Store their indices in two vectors say left and right.
  If there is no smaller rect in the left we can use -1 as an index and for the right len as an index.

• The width will be equal to the right - left - 1.

• Now traverse the heights array and calculate the area for every rect and store the max_area.

Complexity

• Time complexity:O(N)

• Space complexity:O(N)

Code

int largestRectangleArea(vector<int> &heights) {
    int len = heights.size();
    vector<int> left(len, -1), right(len, len);
    stack<pair<int, int>> st;

    // storing the indices of nearest smaller left for each element
    for (int in = 0; in < len; ++in) {
        if (!st.empty() && st.top().second < heights[in]) {
            left[in] = st.top().first;
        } else if (!st.empty() && st.top().second >= heights[in]) {
            while (!st.empty() && st.top().second >= heights[in])
                st.pop();
            if (!st.empty())
                left[in] = st.top().first;
        }
        st.push({in, heights[in]});
    }

    st = stack<pair<int, int>>();

    // storing the indices of nearest right element for each element
    for (int in = len - 1; in >= 0; in--) {
        if (!st.empty() && st.top().second < heights[in]) {
            right[in] = st.top().first;
        } else if (!st.empty() && st.top().second >= heights[in]) {
            while (!st.empty() && st.top().second >= heights[in])
                st.pop();
            if (!st.empty())
                right[in] = st.top().first;
        }
        st.push({in, heights[in]});
    }

    // calculate area for every rectangle by combining the nearer left and rigt and store the maximum area.
    int max_area = 0;
    for (int in = 0; in < len; ++in) {
        int area = heights[in] * (right[in] - left[in] - 1);
        max_area = max(max_area, area);
    }
    return max_area;
}

Please Upvote if you found it helpful.