#84

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Largest Rectangle in Histogram

Find the maximal rectangular area in a histogram using stack-based state management for precise bar tracking and width calculations.

array stack monotonic stack

Problem Statement

You are given an array of integers representing the heights of histogram bars, each with width 1. Your task is to find the area of the largest rectangle that can be formed within the histogram. Each rectangle must be contiguous and fully contained under the histogram bars.

For example, given heights = [2,1,5,6,2,3], the largest rectangle area is 10, covering bars with heights 5 and 6. You must handle large arrays efficiently, considering heights can range up to 10^4 and the array length up to 10^5.

Examples

Example 1

Input: heights = [2,1,5,6,2,3]

Output: 10

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

Example details omitted.

Constraints

1 <= heights.length <= 105
0 <= heights[i] <= 104

Solution Approach

Monotonic Stack for Height Tracking

Use a stack to maintain indices of bars in increasing height order. For each bar, pop from the stack until the top is less than the current height, computing area using popped height and width derived from indices. This ensures each bar contributes to maximal rectangles.

Compute Widths Dynamically

When popping a bar from the stack, calculate the width as the distance between the current index and the index of the new top of the stack minus one. This allows precise width tracking for each potential rectangle, preventing overcounting.

Final Stack Clearance

After iterating through all bars, clear remaining stack entries by treating the end of the array as a zero-height bar. This ensures any potential maximal rectangles ending at the histogram's right edge are considered.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each bar is pushed and popped at most once from the stack. Space complexity is O(n) for storing indices in the stack during the monotonic traversal.

What Interviewers Usually Probe

You might be prompted to explain why a naive O(n^2) approach fails for large histograms.
Clarify how stack state ensures all rectangle widths are computed correctly without missing any bar combinations.
Expect questions on handling equal-height bars and ensuring correct width computation for consecutive duplicates.

Common Pitfalls or Variants

Common pitfalls

Forgetting to add a sentinel zero-height bar to process remaining stack elements.
Incorrect width calculation when the stack becomes empty after popping.
Pushing indices instead of heights can lead to miscalculating rectangle areas.

Follow-up variants

Largest rectangle under skyline silhouette problems, where heights may vary non-uniformly and require similar stack techniques.
Finding maximal square instead of rectangle in a histogram-like 2D matrix using modified state management.
Calculating largest rectangle in a histogram with additional constraints on minimum or maximum allowed heights.

FAQ

What is the optimal approach for Largest Rectangle in Histogram?

The optimal solution uses a monotonic stack to track indices of increasing heights, allowing O(n) area computation for each rectangle.

Why is a stack used instead of nested loops?

Nested loops result in O(n^2) time, which is too slow for large arrays. A stack ensures each bar is considered efficiently once.

How do you handle consecutive bars of equal height?

Consecutive bars of equal height are processed by popping from the stack until the top is strictly less, ensuring correct width calculation for maximal rectangles.

What are common mistakes when implementing this problem?

Mistakes include not adding a sentinel zero-height bar, incorrect width calculation when stack empties, or confusing indices with heights.

Can this stack pattern be reused in other histogram problems?

Yes, any problem requiring contiguous maximal area tracking, like skyline or maximal square variations, benefits from this monotonic stack approach.

terminal

Solution

Solution 1: Monotonic Stack

We can enumerate the height $h$ of each bar as the height of the rectangle. Using a monotonic stack, we find the index $left_i$, $right_i$ of the first bar with a height less than $h$ to the left and right. The area of the rectangle at this time is $h \times (right_i-left_i-1)$. We can find the maximum value.

1

2

3

4

5

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

Solution 2

#### Python3

1

2

3

4

5

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

Continue Practicing

#85 maximal rectangle #42 trapping rain water #321 create maximum number