HardNeetCode150ArrayStackMonotonic Stack
Largest Rectangle in Histogram
Find largest rectangular area.
Examples
Input
heights = [2,1,5,6,2,3]
Output
10
Rectangle of height 5, width 2 = 10.
Constraints
- •
1 <= heights.length <= 10^5 - •
0 <= heights[i] <= 10^4
Approaches
Expand left/right for each bar.
CodeT: O(n^2) | S: O(1)
Track indices where height increases.
CodeT: O(n) | S: O(n) stack
def largestRectangleArea(heights):
stack=[-1]; mx=0
for i in range(len(heights)+1):
h=heights[i] if i<len(heights) else 0
while stack[-1]!=-1 and h<heights[stack[-1]]:
ht=heights[stack.pop()]; w=i-stack[-1]-1
mx=max(mx,ht*w)
stack.append(i)
return mxSame approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Expand left/right for each bar. |
| Monotonic Stack | O(n) | O(n) stack | Track indices where height increases. |
| Monotonic Stack Optimized | O(n) | O(n) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Expand left/right for each bar.
Monotonic Stack
T: O(n)S: O(n) stack
Track indices where height increases.
Monotonic Stack Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling empty stack
Off-by-one in width
Wrong boundary