Largest Rectangle in Histogram

This comprehensive study note explores the optimal solution for finding the Largest Rectangle in a Histogram. Grounded in stack-based data structures, this guide transitions from an intuitive brute-force approach to a highly optimized single-pass linear time algorithm.

1. Problem Statement and Formal Definition

Given an array of integers representing the heights of consecutive bars in a histogram where each bar has a uniform width of 1, determine the maximum possible rectangular area that can be formed within the histogram.

• Target: Return the integer representing the maximum rectangular area.
• Example Analysis:
  • Taking height 2 across width 4 (indices 2 to 5) yields an area of 8.
  • Taking height 5 across width 2 (indices 2 to 3) yields 5 x 2 = 10, which is the maximum possible area in this configuration.

2. Core Mental Model: The Boundary Concept

Real-Life Analogy

Real-Life Analogy: Imagine you are holding a wooden plank of a specific height standing vertically in a row. How far can you stretch this plank to the left and right without hitting a shorter plank that forces your rectangle's top edge to clip? You can extend horizontally as long as the neighboring bars are taller than or equal to your current bar's height. The moment you encounter a bar shorter than yours, your horizontal expansion stops abruptly.

To calculate the maximum rectangle formed by any bar i:

1. Left Boundary: Find the index of the Previous Smaller Element (PSE)—the first shorter bar to the left.
2. Right Boundary: Find the index of the Next Smaller Element (NSE)—the first shorter bar to the right.
3. Width Calculation: $\text{Width} = \text{NSE Index} - \text{PSE Index} - 1$
4. Area Calculation: $\text{Area} = \text{Height}[\text{i}] \times \text{Width}$

3. The Naive (Brute Force) Approach

The most straightforward way to solve this problem is to iterate through every single bar in the histogram, treat each bar as the limiting height of a potential rectangle, and expand outwards to the left and right until a smaller bar is met.

Naive Algorithm Logic

For each index i from 0 to n-1:
    1. Scan left to find the boundary where height < array[i]
    2. Scan right to find the boundary where height < array[i]
    3. Compute width and area: area = height[i] * (right_boundary - left_boundary - 1)
    4. Update global maximum area variable

Complexity Analysis

• Time Complexity: $\mathcal{O}(N^2)$ because for every bar, we potentially scan the entire array left and right.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.

4. Better Approach: Two-Pass Precomputation

To optimize the brute-force search, we can precompute the Next Smaller Element (NSE) and Previous Smaller Element (PSE) arrays beforehand using a monotonic stack.

Step-by-Step Two-Pass Workflow

1. Find NSE Array: Run a linear-time monotonic stack algorithm from right to left (or left to right) to record the index of the next smaller element for every bar. If no smaller element exists on the right, assign the array size n.
2. Find PSE Array: Run a similar monotonic stack algorithm to record the index of the previous smaller element for every bar. If none exists, assign -1.
3. Compute Areas: Iterate through the array once more, applying the width formula using precomputed indices.

Complexity Analysis

• Time Complexity: $\mathcal{O}(4N) \approx \mathcal{O}(N)$ (Two passes for NSE/PSE + one pass for computation).
• Space Complexity: $\mathcal{O}(4N) \approx \mathcal{O}(N)$ (Storage for NSE array, PSE array, and two stack allocations).

5. Optimal Solution: Single-Pass On-The-Fly Algorithm

Can we eliminate precomputation arrays entirely and compute everything in a single pass? Yes, by leveraging a monotonic increasing stack that stores indices instead of values.

How On-The-Fly Computation Works

• As we traverse from left to right, we maintain a stack of indices where corresponding bar heights are in strictly increasing order.
• When we encounter a bar shorter than the bar at the top of our stack, it acts as the Next Smaller Element (NSE) for the stack's top element!
• Simultaneously, the new stack top (after popping) becomes the Previous Smaller Element (PSE).
• This allows us to compute areas dynamically on the fly as elements are popped.

6. Complete Dry Run Walkthrough

Let us trace the optimal single-pass algorithm using the histogram array: [3, 2, 10, 11, 5, 6, 3, 2] (simplified illustrative trace).

Phase 1: Traversing and Processing via Stack Pop Events

• Index 0, Value 3: Stack is empty. Push index 0. (Stack: [0])
• Index 1, Value 2: 2 < 3. We must pop index 0 (height = 3).
  • NSE (bar stopping expansion on the right) = Current index 1.
  • PSE (bar stopping expansion on the left) = Stack becomes empty $\rightarrow -1.
  • Area = $3 \times (1 - (-1) - 1) = 3 \times 1 = 3$.
  • Push index 1 (value = 2). (Stack: [1])
• Index 2, Value 10: 10 > 2. Valid increasing order. Push index 2. (Stack: [1, 2])
• Index 3, Value 11: 11 > 10. Valid increasing order. Push index 3. (Stack: [1, 2, 3])
• Index 4, Value 5: 5 < 11 and 5 < 10. Pop index 3 (11) and index 2 (10), calculating their maximum rectangles using current index 4 as their NSE. Then push index 4 (value = 5).
• Continuing the scan: Elements are pushed and popped whenever a smaller bar breaks the monotonic increasing sequence, updating our global Max Area dynamically.

Phase 2: Emptying Remaining Stack Elements (Clean-up Phase)

When the main loop terminates, some bars remaining in the stack have no smaller element to their right (their NSE is effectively the array length n). We pop them one by one and compute their final rectangular areas:

• NSE for remaining elements = n (array length).
• PSE = the index now sitting below them in the stack (or -1 if stack becomes empty).

7. Optimal Single-Pass Pseudo-Code

Here is the complete, clean functional implementation of the optimized single-pass algorithm:

function largestRectangleArea(heights: number[]): number {
    const stack: number[] = [];
    let maxArea = 0;
    const n = heights.length;

    for (let i = 0; i < n; i++) {
        // Pop elements while current bar is shorter than the bar at stack top
        while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
            const elementIndex = stack.pop()!;
            const height = heights[elementIndex];
            
            // Next smaller element index is current index `i`
            const nse = i;
            // Previous smaller element index is the new stack top, or -1 if empty
            const pse = stack.length === 0 ? -1 : stack[stack.length - 1];
            
            const width = nse - pse - 1;
            const currentArea = height * width;
            
            maxArea = Math.max(maxArea, currentArea);
        }
        stack.push(i);
    }

    // Process remaining elements in the stack (no right smaller element exists)
    while (stack.length > 0) {
        const elementIndex = stack.pop()! ;
        const height = heights[elementIndex];
        
        const nse = n; // Extends all the way to the end
        const pse = stack.length === 0 ? -1 : stack[stack.length - 1];
        
        const width = nse - pse - 1;
        const currentArea = height * width;
        
        maxArea = Math.max(maxArea, currentArea);
    }

    return maxArea;
}

8. Complexity Summary

9. Summary and Key Takeaways

• Problem Core: Finding the largest rectangle in a histogram relies fundamentally on determining the Previous Smaller Element (PSE) and Next Smaller Element (NSE) for every bar.
• Width Formula: Once boundaries are identified, the effective width is calculated cleanly as $\text{NSE} - \text{PSE} - 1$.
• Monotonic Stack Power: Storing indices in a monotonic increasing stack allows us to evaluate boundaries dynamically without needing extra precomputation arrays.
• On-The-Fly Evaluation: Popping an element from the stack happens precisely when a shorter bar is encountered, which acts as its right boundary (NSE).
• Clean-Up Phase: Elements remaining in the stack at the end of traversal have no right-side barrier, so their NSE defaults to the total array length n.
• Optimal Efficiency: The single-pass stack solution achieves an optimal $\mathcal{O}(N)$ time complexity and $\mathcal{O}(N)$ space complexity, satisfying interview and production standards.