84. Largest Rectangle in Histogram

Difficulty: Hard
Category: Stack, Monotonic Stack

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.

Examples

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

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

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Rectangle definition: What rectangles can we form? (Assumption: Rectangles formed by consecutive bars - width is number of consecutive bars, height is minimum bar height)

  2. Rectangle area: How is rectangle area calculated? (Assumption: width × height - number of bars × minimum bar height in range)

  3. Optimization goal: What are we optimizing for? (Assumption: Maximum area among all possible rectangles)

  4. Return value: What should we return? (Assumption: Integer representing maximum rectangle area)

  5. Empty histogram: What if histogram is empty? (Assumption: Per constraints, length >= 1, so not empty)

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Initial Thought: “I need to find largest rectangle. Let me check all possible rectangles.”

Naive Solution: For each bar, try all possible widths (extend left and right), compute area, track maximum.

Complexity: O(n²) time, O(1) space

Issues:

  • O(n²) time - inefficient
  • Repeats work for finding boundaries
  • Doesn’t leverage monotonic stack
  • Can be optimized

Step 2: Semi-Optimized Approach (10 minutes)

Insight: “I can use DP to find left and right boundaries where current bar is minimum.”

Improved Solution: For each bar, find leftmost and rightmost positions where it’s minimum. Use DP or two passes to compute boundaries.

Complexity: O(n²) worst case, O(n) space

Improvements:

  • Better structure than brute-force
  • Still O(n²) in worst case
  • Can optimize boundary finding

Step 3: Optimized Solution (12 minutes)

Final Optimization: “I can use monotonic stack to find boundaries efficiently.”

Best Solution: Use monotonic stack to find left and right boundaries where each bar is minimum. Stack stores indices. When bar is smaller than stack top, pop and compute area.

Complexity: O(n) time, O(n) space

Key Realizations:

  1. Monotonic stack is perfect for “next smaller” problems
  2. O(n) time is optimal - each bar processed once
  3. Stack efficiently finds boundaries
  4. O(n) space for stack is necessary

Approach

This is a classic Monotonic Stack problem. The key insight is that for each bar, we need to find the largest rectangle that can be formed with that bar as the height.

Algorithm:

  1. Use a stack to store indices of bars in increasing order of height
  2. For each bar, pop all bars from stack that are taller than current bar
  3. Calculate area for each popped bar using its height and the width it can extend
  4. Add a sentinel (height 0) at the end to ensure all bars are processed
  5. Track maximum area found so far

Key Insight:

  • For each bar at index i, the largest rectangle with height heights[i] extends from the previous smaller bar to the next smaller bar
  • The width = right_boundary - left_boundary - 1

Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int max_area = 0;
        heights.push_back(0); 
        int n = heights.size();
        stack<int> stk;
        for(int i = 0; i < n; i++) {
            while(!stk.empty() && heights[i] < heights[stk.top()]) {
                int height = heights[stk.top()];
                stk.pop();
                int width = stk.empty()? i: i - stk.top() - 1;
                max_area = max(max_area, height * width);
            }
            stk.push(i);
        }
        return max_area;
    }
};

Explanation

Step-by-Step Process:

  1. Add Sentinel: Append 0 to heights to ensure all bars are processed
  2. Initialize: Empty stack and max_area = 0
  3. For each bar:
    • Pop taller bars: While stack is not empty and current bar is shorter than stack top
    • Calculate area: For each popped bar, calculate area = height × width
    • Update max: Keep track of maximum area found
    • Push current: Add current index to stack

Width Calculation:

  • If stack is empty: Width extends from start to current position = i
  • If stack not empty: Width extends from previous smaller bar to current = i - stk.top() - 1

Example Walkthrough:

For heights = [2,1,5,6,2,3] with sentinel [2,1,5,6,2,3,0]:

  • i=0, height=2: Stack=[0]
  • i=1, height=1: Pop 0, area=2×1=2, Stack=[1]
  • i=2, height=5: Stack=[1,2]
  • i=3, height=6: Stack=[1,2,3]
  • i=4, height=2: Pop 3, area=6×1=6; Pop 2, area=5×2=10; Stack=[1,4]
  • i=5, height=3: Stack=[1,4,5]
  • i=6, height=0: Pop all, calculate remaining areas

Maximum area = 10

Complexity Analysis

Time Complexity: O(n) where n is the length of heights array

  • Each element is pushed and popped from stack exactly once
  • Each element is processed once

Space Complexity: O(n) for the stack

  • In worst case, all elements could be in increasing order

Key Insights

  1. Monotonic Stack: Maintains bars in increasing height order
  2. Sentinel Value: Adding 0 at end ensures all bars are processed
  3. Area Calculation: Width = distance between smaller bars on left and right
  4. Index Tracking: Store indices in stack, not values, to calculate width
  5. Greedy Approach: Process each bar as soon as we find a smaller bar

Alternative Approaches

Brute Force (O(n²)):

int largestRectangleArea(vector<int>& heights) {
    int max_area = 0;
    for(int i = 0; i < heights.size(); i++) {
        int min_height = heights[i];
        for(int j = i; j < heights.size(); j++) {
            min_height = min(min_height, heights[j]);
            max_area = max(max_area, min_height * (j - i + 1));
        }
    }
    return max_area;
}

Divide and Conquer (O(n log n)):

int largestRectangleArea(vector<int>& heights) {
    return divideConquer(heights, 0, heights.size() - 1);
}

int divideConquer(vector<int>& heights, int left, int right) {
    if(left > right) return 0;
    if(left == right) return heights[left];
    
    int min_idx = left;
    for(int i = left; i <= right; i++) {
        if(heights[i] < heights[min_idx]) min_idx = i;
    }
    
    int area = heights[min_idx] * (right - left + 1);
    int left_area = divideConquer(heights, left, min_idx - 1);
    int right_area = divideConquer(heights, min_idx + 1, right);
    
    return max({area, left_area, right_area});
}

The monotonic stack approach is the most efficient solution for this problem, demonstrating the power of this data structure for solving range-based problems.