Stack Operations
What is this?
Stand in front of a city skyline and pick one building. How wide a banner could you hang at exactly that building's height? You can stretch left until a shorter building blocks you, and right until another does. The two nearest shorter buildings define your banner. Do that for every building and take the biggest banner. That is the largest rectangle under a histogram, and the monotonic stack finds both boundaries for every bar in a single pass.
Fun fact: Maximal Rectangle is a hard problem that is really a solved one in disguise. Treat each row of the binary matrix as the ground line of a histogram whose bar heights are the counts of consecutive
1s above, then run the histogram algorithm once per row. A problem that looks two-dimensional collapses intomcalls to something you already wrote, forO(m × n)total.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The idea in one line: keep a stack of indices whose heights are increasing. When a shorter bar arrives, everything taller must stop. The moment each is popped you know both of its boundaries, so its rectangle is settled for good.
1. Why increasing, and why the pop is the answer
While heights increase, nothing is resolved: a taller bar might extend arbitrarily far right. The instant a shorter bar arrives, every taller bar on the stack has met its right boundary, which is the new bar. And its left boundary is whatever sits below it on the stack, since the stack is increasing.
stack, best = [], 0 # stack holds indices
for i, h in enumerate(heights + [0]): # sentinel 0 flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1 # nearest shorter on the left
best = max(best, height * (i - left - 1))
stack.append(i)
The i - left - 1 is the line to understand: the rectangle spans strictly between the two shorter bars, so both boundaries are excluded. And the appended 0 sentinel guarantees every bar is eventually popped. Without it, an increasing input leaves the whole stack unresolved and the answer is zero.
2. A 30-second worked example
heights = [2, 1, 5, 6, 2, 3]
The winning rectangle is height 5 across indices 2 and 3 (area 10). It was settled when the bar of height 2 at index 4 arrived and popped the 5, before the scan finished.
3. The greedy variant
Remove K Digits uses the same increasing-stack machinery for a different goal. To make the smallest possible number, walk the digits and pop any digit larger than the incoming one while removals remain: a bigger digit in a more significant position always hurts more than anything it could gain later. Two details finish it. If removals are left over at the end, drop them from the tail (the digits are already non-decreasing, so the largest are last), and strip leading zeros before returning.
4. Where you'll actually meet this
- Layout and floorplans. Finding the largest empty axis-aligned rectangle in an occupancy grid (free area on a page or a floor) is Maximal Rectangle when the grid is a 0/1 matrix.
- Skyline profiles. The widest region that fits under a height profile is the histogram problem directly.
- Choosing digits to keep. Dropping
kdigits from a numeric string to get the smallest value is the greedy stack in Remove K Digits.
5. Problems in this chapter
Largest Rectangle in Histogram
Largest rectangle fitting under a bar chart. The chapter's centrepiece: the monotonic stack finds both boundaries for every bar in one pass.
Pattern: increasing monotonic stack + sentinel. Target: O(n) time, O(n) space.
Maximal Rectangle
Largest all-ones rectangle in a binary matrix. Build a running histogram of consecutive ones per column and call the previous algorithm once per row.
Pattern: row-wise reduction to the histogram problem. Target: O(m × n) time, O(n) space.
Remove K Digits
Remove k digits to leave the smallest possible number. Same increasing-stack sweep, greedy pop rule, plus tail-trimming and leading-zero handling.
Pattern: greedy monotonic stack. Target: O(n) time, O(n) space.
6. Common pitfalls
- Omitting the sentinel. A non-decreasing input leaves every bar on the stack and the answer comes back wrong (often 0). Append a zero height or run one extra iteration.
- Storing heights instead of indices. Widths need positions; a stack of heights cannot reconstruct them.
- Getting the width formula wrong. It is
i - stack[-1] - 1after popping, with-1standing in for "no shorter bar to the left", noti - popped_index. - Mixing
>and>=on equal heights. Either is correct as long as the sweep ends with a flush. With>=, equal bars pop each other and the last one carries the full width. - Rebuilding the histogram per row in Maximal Rectangle. Update it incrementally: a
1increments the column's height, a0resets it to zero. - Forgetting leftover removals in Remove K Digits, and forgetting to strip the leading zeros afterwards.
- Returning an empty string rather than
"0"when everything is removed.
7. Key takeaways
- Two boundaries define an area, and the monotonic stack delivers both for every element in O(n).
- The pop is the moment of knowledge: that is when an element's right boundary finally exists.
- A sentinel guarantees resolution. Nothing may be left on the stack when the input ends.
- Reduce two dimensions to one. Each matrix row is a histogram; do not invent a 2-D algorithm.
- Indices, not values. Everything geometric depends on positions.
- The same sweep serves a greedy goal: smallest-number digit removal is the identical loop with a different pop rule.
- Why interviewers like it: the O(n²) brute force is easy, the O(n) needs a real invariant, and the matrix version tests whether you can recognise a solved problem wearing a disguise.
Order: Largest Rectangle in Histogram → Maximal Rectangle → Remove K Digits.