Problem Description

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.

Example

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.

Solution Approach

Key Insight

The key insight is that for each bar, we want to find:

1. Next Smaller Element (NSE): The first bar to the right that is smaller than the current bar

2. Previous Smaller Element (PSE): The first bar to the left that is smaller than the current bar

Once we know these boundaries, the width of the rectangle that can be formed with the current bar as the height is:

width = (nextSmallerIndex - 1) - (previousSmallerIndex + 1) + 1
      = nextSmallerIndex - previousSmallerIndex - 1

The area would be: width * heights[i]

Why Monotonic Stack?

This problem is a perfect application of monotonic stacks:

We need to find the next/previous smaller element efficiently

A naive O(n²) approach would check every bar for each bar

Monotonic stacks allow us to find these boundaries in O(n) time

Thought Process

1. Find Next Smaller Element (NSE):

- Use a monotonic increasing stack (larger elements on top)

- Iterate from right to left

- For each bar, pop all bars that are >= current bar

- The top of the stack (if exists) is the next smaller element to the right

2. Find Previous Smaller Element (PSE):

- Use a monotonic increasing stack

- Iterate from left to right

- For each bar, pop all bars that are >= current bar

- The top of the stack (if exists) is the previous smaller element to the left

3. Calculate Maximum Area:

- For each bar, calculate the rectangle area using the boundaries found

- Track the maximum area

Code Solution

python

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        ns = [n]*n  # next smaller index (default to n if none found)
        ps = [-1]*n  # previous smaller index (default to -1 if none found)
        
        # Find next smaller element (right to left)
        stack = []
        for i in range(n-1, -1, -1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                ns[i] = stack[-1]
            stack.append(i)
        
        # Find previous smaller element (left to right)
        stack = []
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                ps[i] = stack[-1]
            stack.append(i)
        
        # Calculate maximum area
        ans = 0
        for i in range(n):
            # Width = (nextSmaller - 1) - (previousSmaller + 1) + 1
            #      = nextSmaller - previousSmaller - 1
            cur = (ns[i] - ps[i] - 1) * heights[i]
            ans = max(ans, cur)
        
        return ans

Detailed Explanation

Step-by-Step Walkthrough

Let's trace through the example heights = [2,1,5,6,2,3]:

Step 1: Find Next Smaller Element (NSE)

Iterate from right to left with a monotonic increasing stack:

Index	Height	Stack Before	Action	NSE
5	3	[]	Push 5	6 (default)
4	2	[5]	Pop 5 (3 >= 2), Push 4	6
3	6	[4]	Push 3	4
2	5	[4, 3]	Push 2	3
1	1	[4, 3, 2]	Pop all (all >= 1), Push 1	6
0	2	[1]	Push 0	1

Result: ns = [1, 6, 3, 4, 6, 6]

Step 2: Find Previous Smaller Element (PSE)

Iterate from left to right with a monotonic increasing stack:

Index	Height	Stack Before	Action	PSE
0	2	[]	Push 0	-1
1	1	[0]	Pop 0 (2 >= 1), Push 1	-1
2	5	[1]	Push 2	1
3	6	[1, 2]	Push 3	2
4	2	[1, 2, 3]	Pop 3, 2 (6,5 >= 2), Push 4	1
5	3	[1, 4]	Push 5	4

Result: ps = [-1, -1, 1, 2, 1, 4]

Step 3: Calculate Areas

Index	Height	NSE	PSE	Width	Area
0	2	1	-1	1-(-1)-1 = 1	2×1 = 2
1	1	6	-1	6-(-1)-1 = 6	1×6 = 6
2	5	3	1	3-1-1 = 1	5×1 = 5
3	6	4	2	4-2-1 = 1	6×1 = 6
4	2	6	1	6-1-1 = 4	2×4 = 10
5	3	6	4	6-4-1 = 1	3×1 = 3

Maximum Area: 10 ✓

Why This Works

1. Monotonic Stack Property: The stack maintains elements in increasing order, allowing us to efficiently find the next/previous smaller element.

2. Boundary Detection:

- When we pop an element, it means we've found a smaller element (the current one)

- The element at the top of the stack (after popping) is the boundary we're looking for

3. Width Calculation:

- ns[i] is the first index to the right where height is smaller

- ps[i] is the first index to the left where height is smaller

- The rectangle can extend from ps[i] + 1 to ns[i] - 1

- Width = (ns[i] - 1) - (ps[i] + 1) + 1 = ns[i] - ps[i] - 1

Time & Space Complexity

Time Complexity: O(n)

- Each element is pushed and popped from the stack at most once

- Three passes through the array: O(n) each

Space Complexity: O(n)

- Stack: O(n) in worst case

- Arrays for NSE and PSE: O(n) each

Key Takeaways

1. Monotonic stacks are perfect for finding next/previous smaller/greater elements

2. Two-pass approach: Find boundaries first, then calculate areas

3. Default values matter: Using n for NSE and -1 for PSE handles edge cases where no smaller element exists

4. Width calculation: width = nextSmallerIndex - previousSmallerIndex - 1

Leetcode 84. Largest Rectangle in Histogram