Largest Rectangle in Histogram hard

Problem Statement

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

Example 1

Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The largest rectangle is shown in the figure above. It has a height of 5 and a width of 2, so its area is 5 * 2 = 10.

Example 2

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

Steps to Solve

The core idea is to use a stack to keep track of indices of bars. We iterate through the heights array. For each bar:

1. While the stack is not empty and the current bar's height is less than or equal to the height of the bar at the top of the stack: This means the current bar limits the height of the rectangle that can be formed using the bars at the top of the stack. We pop the top element from the stack.
2. Calculate the area: For each popped bar, its area is calculated as height[stack.top()] * (stack.empty() ? i : i - stack.top() -1). The width is either the current index i (if the stack is empty) or the difference between the current index and the index of the next smaller bar (the top of the stack). We update the maximum area if needed.
3. Push the current bar's index onto the stack: This prepares for future calculations.
4. After iterating through all bars: We need to handle any remaining bars in the stack by repeating step 2, considering the width extends to the end of the array.

Explanation

The stack maintains a monotonically increasing sequence of indices. When we encounter a bar shorter than the bar at the top of the stack, it means that the bars at the top of the stack can form a rectangle with the current bar as its right boundary. This is because any bar that is taller than the current bar would have been pushed to the stack earlier. We pop those taller bars to calculate their areas and find the maximum.

Code (C++)

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    int maxArea = 0;
    int n = heights.size();

    for (int i = 0; i <= n; ++i) {
        int h = (i == n ? 0 : heights[i]); // Treat the end as a bar of height 0

        while (!s.empty() && h < heights[s.top()]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : i - s.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        s.push(i);
    }
    return maxArea;
}

Complexity

• Time Complexity: O(N), where N is the number of bars in the histogram. Each bar is pushed and popped at most once onto the stack.
• Space Complexity: O(N) in the worst case, as the stack could potentially hold all the indices. In the best case it will be O(1) if the heights are monotonically increasing.