Largest Rectangle In Histogram

Problem

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Examples

Example 1:

Input: heights = [7,1,7,2,2,4]

Output: 8

Example 2:

Input: heights = [1,3,7]

Output: 7

Constraints

• 1 <= heights.length <= 1000.
• 0 <= heights[i] <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Solution

We perform multiple passes, tracking the left and right boundaries for each index. A final pass then lets us find the width and thus area.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        const int N = heights.size();
 
        // leftMost[i] stores index of nearest bar to the left of i
        //   that is strictly smaller than height[i]
        std::vector<int> leftMost(N, -1);
        // rightMost[i] stores index of nearest bar to the right of i
        //   that is strictly smaller than height[i]
        std::vector<int> rightMost(N, N);
 
        std::stack<int> st;
 
        // Find nearest strictly smaller bar on the left for each i
        for (int i = 0; i < N; ++i) {
            // Remove bars that are >= height
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                st.pop();
            }
            // If stack is non-empty, top is nearest index to left with small height
            if (!st.empty()) { leftMost[i] = st.top(); }
            // Add current bar for future bars to consider
            st.push(i);
        }
 
        // Clear stack so we can resuse for right side
        while (!st.empty()) { st.pop(); }
 
        // Find nearest strictly smaller bar to the right for each i
        for (int i = N - 1; i >= 0; --i) {
            // Remove bars that are >= height
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                st.pop();
            }
            // If stack is non-empty, top is nearest index to left with small height
            if (!st.empty()) { rightMost[i] = st.top(); }
            // Add current bar for future bars to consider
            st.push(i);
        }
 
        int max_area = 0;
        for (int i = 0; i < N; ++i) {
            // First smaller bars are exclusded from the rectangle
            int width = rightMost[i] - leftMost[i] + 1 - 2;
            int area = heights[i] * width;
            max_area = std::max(max_area, area);
        }
 
        return max_area;
    }
};