Two Pointers — Largest Rectangle in Histogram
↗ LeetCode: Largest Rectangle in Histogram · Hard · pattern chapter →
Asked atAmazonGoogleMicrosoftMetaAdobe
Given bar heights, return the largest rectangle contained.
Example 1 — heights=[2,1,5,6,2,3] → 10Example 2 — heights=[2,4] → 4
Constraints — 1 ≤ n ≤ 10⁵. Brute enumerates every (l, r) window in O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Monotonic stack runs each index in amortised O(1) → O(n) = 10⁵ ops = <10 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — For each bar expand outward
O(n²). Baseline.
Approach 2 — Monotonic increasing stack (canonical)
Insight. When we push bar i and pop t (because h[i] < h[t]), both boundaries of t's maximal rectangle are known: next smaller = i, previous smaller = stack.peek() after pop.
Sentinel trick. Iterate i from 0 to n inclusive with h=0 at end to flush the stack.
java
int largestRectangleArea(int[] h) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0, n = h.length;
for (int i = 0; i <= n; i++) {
int val = i == n ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] > val) {
int t = st.pop();
int w = st.isEmpty() ? i : i - st.peek() - 1;
best = Math.max(best, h[t] * w);
}
st.push(i);
}
return best;
}Execution Trace
Complexity — Time O(n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Expand | O(n²) | O(1) | baseline |
| Mono stack | O(n) | O(n) | canonical |
When to use which
- "Largest rectangle" → mono stack + sentinel.
- 2D binary matrix → row heights + this template (see Maximal Rectangle).
- "Range max/min queries" → sparse table or seg tree.
AI Study CompanionBeta
Related problems
Was this page helpful?