Largest Rectangle in Histogram
Problem Description
Given an array of integers heights representing the histogram's bar heights (each bar width = 1), return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10 (bars at index 2,3 with height 5, width 2)
Example 2:
Input: heights = [2,4]
Output: 4
DE Shaw Tier 2 — LC 84.
Optimal: Monotonic stack O(n). Maintain an increasing stack of indices. When current bar is shorter than stack top, pop and compute area using the popped bar as the shortest — width extends from current stack top+1 to current index-1.
Talk-track: 'Each bar is pushed and popped once → O(n). The stack encodes: for each bar, what is the rightward extent before a shorter bar blocks it.'
Example Test Cases
Example 1
Input: [[2,1,5,6,2,3]]
Expected: 10
Example 2
Input: [[2,4]]
Expected: 4
Example 3
Input: [[1]]
Expected: 1
Example 4
Input: [[4,2,0,3,2,5]]
Expected: 6
Run your code to see the results