This problem requires calculating the largest rectangle in a histogram represented by an array of bar heights. The most efficient approach uses a monotonic stack to track indices and heights, allowing rapid width computation for each rectangle. By maintaining stack state carefully, you can avoid redundant calculations and ensure linear time performance.
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.
How GhostInterview Helps
- Guides through stack state management with detailed examples for accurate width and area calculation.
- Highlights subtle failure modes like missing the final rectangle when the stack is not cleared.
- Provides step-by-step reasoning for each bar, ensuring understanding of monotonic stack pattern and interview expectations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Largest Rectangle in Histogram instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Largest Rectangle in Histogram from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the largest rectangle of 1's in a binary matrix using dynamic programming and stack-based state transitions efficiently.
Open problem page#42 Trapping Rain WaterCalculate the total trapped rain water using the elevation map array, leveraging dynamic programming and two-pointer patterns efficiently.
Open problem page#321 Create Maximum NumberCreate Maximum Number involves merging digits from two arrays while preserving order, maximizing the resulting number.
Open problem page