Skip to main content

Largest Rectangle in Histogram

Problem​

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> indexes(n);
        vector<int> ans(n);

        stack<pair<int, int>> st;
        st.push({-1, n});

        for (int i = n - 1; i >= 0; i--) {
            while (st.top().first >= heights[i]) st.pop();
            indexes[i] = st.top().second;
            st.push({heights[i], i});
            ans[i] = (indexes[i] - i) * heights[i];
        }

        while (!st.empty()) st.pop();
        st.push({-1, -1});
        int area = 0;

        for (int i = 0; i < n; i++) {
            while (st.top().first >= heights[i]) st.pop();
            indexes[i] = st.top().second;
            st.push({heights[i], i});
            ans[i] = ans[i] + heights[i] * (i - indexes[i]) - heights[i];
            area = max(ans[i], area);
        }

        return area;
    }
};