ASAPUtils
The signal
For each height, find how far it can extend before a shorter bar blocks it on each side. Brute force recomputes those boundaries. An increasing stack delays a height until the first shorter bar to its right makes its full width known.
Derivation
Suppose (start, height) is on the stack and current index i has a shorter height.
- The rectangle cannot cross
i. - It has remained valid from
startthroughi - 1. - Its width is
i - start. - Its finished candidate area is
height * (i - start).
After popping it, the current shorter height can start at the popped start, because every bar in
that range was at least as tall as the current height. That is the non-obvious line.
int largestRectangleArea(vector<int>& heights) {
vector<pair<int,int>> st; // {start, height}
int best = 0;
for (int i = 0; i <= (int)heights.size(); i++) {
int current = i == heights.size() ? 0 : heights[i];
int start = i;
while (!st.empty() && st.back().second > current) {
auto [s, height] = st.back(); st.pop_back();
best = max(best, height * (i - s));
start = s;
}
if (i < heights.size()) st.push_back({start, current});
}
return best;
}
function largestRectangleArea(heights) {
const stack = []; // [start, height]
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const current = i === heights.length ? 0 : heights[i];
let start = i;
while (stack.length && stack.at(-1)[1] > current) {
const [s, height] = stack.pop();
best = Math.max(best, height * (i - s));
start = s;
}
if (i < heights.length) stack.push([start, current]);
}
return best;
}
Why [5, 6] produces area 10
When height 2 arrives after 5 and 6, it pops 6 first: width 1, area 6. Then it pops 5: width 2, area 10. The shorter bar exposes the complete right boundary for both heights; the stored starts provide their left boundaries.
Complexity
O(n) time by the push-once/pop-once argument. O(n) space for an increasing histogram.
Traps
- Forgetting
start = poppedStart; this loses the width carried through taller bars. - Forgetting to flush the stack at the end. Use a virtual zero sentinel.
- Using the current height when calculating a popped rectangle’s area.
- Memorising code without the invariant. On paper, label every stack entry
(earliest start, height)and the implementation becomes derivable.
Blank re-solve prompt
Derive the O(n) solution from “first shorter bar closes a rectangle.” Explain the carried start and sentinel before writing any syntax.