Largest Rectangle in histogram

XXX. Largest Rectangle in Histogram

Stack

Monotonic Stack

Problem Statement:

Given an array of integers heights representing the heights of bars in a histogram, find the area of the largest rectangle that can be formed within the histogram.

Approach:

1. Use a monotonic increasing stack to track the indices of histogram bars.
2. Every time a bar with a lower height than the stack's top is encountered, calculate the area for the height represented by the top of the stack.
3. To simplify edge cases, add a sentinel value (-1) to the stack at the beginning, which helps in area calculation when popping elements.
4. Iterate through the heights array. For each height:
   • If the stack is empty or the current height is greater than or equal to the height at the top index of the stack, push the index.
   • Otherwise, calculate the area for the height at the top of the stack and update the maximum area.
5. Finally, process any remaining indices in the stack to account for heights extending to the end of the array.

Java Implementation:

// Not too hard of a problem, just some tricky details that will be hard to reengineer.
// Key point: Every pop from the stack will result in an "Area Calculation Event"
// Because if we have a decreasing height, we can't build any rectangles with the previous heights.
public int largestRectangleArea(int[] heights) {
    Stack stack = new Stack<>();
    int max = 0; // Variable to track the maximum area
    int area = 0;
    int i = 0;

    // Optimization: Push a sentinel value (-1) to avoid checking if the stack is empty.
    stack.push(-1);

    for (i = 0; i < heights.length;) {
        // If the current height is greater than or equal to the height at the stack's top, push the index.
        if (stack.peek() == -1 || heights[i] >= heights[stack.peek()]) {
            stack.push(i++);
        } else {
            // Pop the top of the stack and calculate the area with the height at the top as the smallest height.
            int top = stack.pop();
            area = heights[top] * (i - stack.peek() - 1);
            max = Math.max(area, max);
        }
    }

    // Process the remaining elements in the stack after iterating through the array.
    while (stack.peek() != -1) {
        int top = stack.pop();
        area = heights[top] * (i - stack.peek() - 1);
        max = Math.max(area, max);
    }

    return max;
}
        

Key Insights:

• **Why use a monotonic stack?** The stack ensures we only calculate areas when a rectangle can no longer be extended with the current height.
• **Role of the sentinel (-1):** The sentinel simplifies edge case handling by acting as a boundary for calculating widths.
• **Why iterate again at the end?** Remaining indices in the stack represent heights that extend to the array's end, so they need separate processing.

Complexity Analysis:

Time Complexity: O(n), because each index is pushed and popped from the stack at most once.
Space Complexity: O(n), due to the space required by the stack.