Neural Mastery
← Practice
Largest Rectangle in Histogram (Monotonic Stack)hard

Largest Rectangle in Histogram (Monotonic Stack)

hard Coding Interview Patterns 20–25 min

NumPy allowed · plain Python earns 10 bonus points

Compute the maximal rectangular area bounding contiguous histogram columns in strict linear time.

Related Skills

Task

Implement largest_rectangle_area(heights): find the area of the largest rectangle that can be formed within the given histogram bar heights. Must run in O(n) time using a monotonic increasing stack.

Function Signature

largest_rectangle_area(heights: list[int]) -> int

Examples

Example 1: Classic Histogram
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Example 2: Two Equal Bars
Input: heights = [2, 4]
Output: 4
Example 3: Single Bar
Input: heights = [7]
Output: 7

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • Runs in linear O(n) time and O(n) space.
  • Heights are non-negative integers.
Python3Saved ✓
def largest_rectangle_area(heights: list[int]) -> int:
"""Find the area of the largest rectangle in histogram heights in O(n) time using a stack."""
# Your implementation here
pass

Case 1: Classic Histogram
Input: heights = [2, 1, 5, 6, 2, 3]
Expected: 10
Case 2: Two Equal Bars
Input: heights = [2, 4]
Expected: 4
Case 3: Single Bar
Input: heights = [7]
Expected: 7