MANG Problem #26: Largest Rectangle in Histogram (Hard)

1. Problem Statement

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.

Input: heights = [2,1,5,6,2,3]
Output: 10 (The rectangle is formed by bars 5 and 6 with height 5 and width 2).

2. Approach: Monotonic Increasing Stack

A rectangle's area is determined by the shortest bar in that range. For every bar, we want to find how far it can extend to the left and right before hitting a bar shorter than itself.

The Goal: Find the index of the first smaller element to the left (L) and the first smaller element to the right (R).
Width: R - L - 1.
Area: heights[curr] * width.
Optimization: Instead of two passes, we use a stack to track indices of bars in increasing order. When we see a bar smaller than the top of the stack, we know the "Right boundary" for the top bar has been found.

3. Java Implementation

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1); // Sentinel for left boundary
    int maxArea = 0;

    for (int i = 0; i < n; i++) {
        // While current height is smaller than top of stack
        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
            int currentHeight = heights[stack.pop()];
            int currentWidth = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, currentHeight * currentWidth);
        }
        stack.push(i);
    }

    // Process remaining bars in stack
    while (stack.peek() != -1) {
        int currentHeight = heights[stack.pop()];
        int currentWidth = n - stack.peek() - 1;
        maxArea = Math.max(maxArea, currentHeight * currentWidth);
    }
    return maxArea;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: For any bar H, the largest rectangle using H as its height is limited by the first bars to its left and right that are shorter than H.
The Stack Logic: We push indices onto the stack as long as heights are increasing. As soon as we see a "drop" in height, we know the rectangle for the taller bars "ends" here.
The Width Formula: If the stack top is i and the previous element in the stack is j, and we are currently at index k, the width for bar i is k - j - 1.

5. Interview Discussion

Interviewer: "Why use -1 in the stack?"
You: "It acts as a sentinel representing the virtual wall at index -1. This simplifies the width calculation when a bar can extend all the way to the start of the histogram."
Interviewer: "What is the time complexity?"
You: "O(N). Every index is pushed and popped exactly once."