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 the clearest example in the curriculum of a hard problem being 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 and intimidating collapses into m calls to something you already wrote, for O(m × n) total.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: keep a stack of indices whose heights are increasing. When a shorter bar arrives, everything taller must stop — and the moment each is popped you know both of its boundaries, so you can settle its rectangle immediately and forever.

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 — it 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 worth pausing on: 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]

i=0 h=2   stack empty            push 0            stack=[0]
i=1 h=1   heights[0]=2 >= 1  →  pop 0: height 2, left=-1, width 1-(-1)-1=1, area 2
                                push 1            stack=[1]
i=2 h=5   5 > 1                  push 2            stack=[1,2]
i=3 h=6   6 > 5                  push 3            stack=[1,2,3]
i=4 h=2   heights[3]=6 >= 2  →  pop 3: h 6, left=2, width 4-2-1=1, area 6
          heights[2]=5 >= 2  →  pop 2: h 5, left=1, width 4-1-1=2, area 10  ✅
                                push 4            stack=[1,4]
i=5 h=3   3 > 2                  push 5            stack=[1,4,5]
i=6 h=0   (sentinel)             pop 5: h 3, left=4, width 6-4-1=1, area 3
                                 pop 4: h 2, left=1, width 6-1-1=4, area 8
                                 pop 1: h 1, left=-1, width 6-(-1)-1=6, area 6
                                                            best = 10

The winning rectangle is height 5 across bars 2 and 3 — and notice it was settled at the moment bar 2 was popped, long 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 increasing, so the largest are last), and strip leading zeros before returning.

4. Where you'll actually meet this

• Image and document analysis. Finding the largest blank rectangle on a scanned page — for stamp placement, watermarking or OCR layout — is Maximal Rectangle verbatim.
• Warehouse and floorplan software. Largest usable free area within an occupancy grid.
• Skyline and terrain queries. Maximum uniform-height region under a profile, in rendering and GIS.
• Resource scheduling. Largest block of time during which at least k machines were free is the histogram problem over an availability timeline.
• Number formatting and pricing. The greedy digit removal is how "shorten this identifier while keeping it smallest" rules are implemented.

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] - 1 after popping, with -1 standing in for "no shorter bar to the left" — not i - popped_index.
• Using > instead of >= on equal heights. Either is workable, but equal bars must be handled consistently or duplicate heights produce short rectangles.
• Rebuilding the histogram per row in Maximal Rectangle. Update it incrementally: a 1 increments the column's height, a 0 resets 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

1. Two boundaries define an area, and the monotonic stack delivers both for every element in O(n).
2. The pop is the moment of knowledge — that is when an element's right boundary finally exists.
3. A sentinel guarantees resolution. Nothing may be left on the stack when the input ends.
4. Reduce two dimensions to one. Each matrix row is a histogram; do not invent a 2-D algorithm.
5. Indices, not values. Everything geometric depends on positions.
6. The same sweep serves a greedy goal — smallest-number digit removal is the identical loop with a different pop rule.
7. 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.