Monotonic Stack & Queue Patterns

A stack can store unresolved questions, rather than just values. You will implement NextGreaterElements and LargestRectangleArea. Begin with an array of indices and explain what information disappears when an index is popped. The two exercises use different pop meanings and different equality rules.

Next greater means first later and strictly greater

Keep unresolved indices in increasing index order and nonincreasing value order. With duplicates, “strictly decreasing” would be an inaccurate invariant. A new value v resolves every top index j with nums[j] < v. Set answer[j]=v, then pop j. A surviving equal value is still waiting for something larger.

Trace [3,3,1,4,2]; i:v denotes an index and its value:

New index	Stack after processing	Newly resolved answers
0	[0:3]	none
1	[0:3,1:3]	none; 3 is not greater than 3
2	[0:3,1:3,2:1]	none
3	[3:4]	answer[2]=4, answer[1]=4, answer[0]=4
4	[3:4,4:2]	none

Output is [4,4,4,-1,-1]. Why is 4 the first later greater value for each popped index? Every intervening value was processed already; if any had been greater, it would have popped that index earlier. Storing only values loses the output destination and collapses equal entries with different positions. The -1 output is a sentinel when none exists; it may also be a real next value for a smaller negative input, which this value-only API intentionally permits.

Histogram pops finalize a right boundary

For a histogram, keep indices of nondecreasing heights. On a strictly lower current height, pop taller bars. Let the popped height be h, current index i, and the new top be j (or -1 when empty). The candidate rectangle spans j+1 ... i-1, so its width is i-j-1. The current shorter bar is excluded.

For [2,4,4,1]:

Event	Remaining stack	Candidate
Read first three bars	[0,1,2]	no right boundary yet
At i=3, pop index 2	[0,1]	h=4, width=1, area=4
Still at i=3, pop index 1	[0]	h=4, width=2, area=8
Still at i=3, pop index 0	[]	h=2, width=3, area=6
Push index 3; reach end i=4	[] after final pop	h=1, width=4, area=4

Maximum area is 8. Notice that j can have equal height for the first pop. Calling both boundaries “strictly smaller” is wrong for this strict-pop variant. The earlier equal bar is popped later and receives the wider span. Alternatively you can pop on equality, but then reason consistently about which equal bar owns the shared span; do not combine formulas from incompatible invariants.

Process a virtual final height 0 at i=n or explicitly flush remaining bars with right boundary n. Nonnegative zero-height bars may remain under a strict-pop rule, but contribute no area. Do not read heights[n]: the sentinel is virtual, and an implementation that appends its index must not dereference it afterward. An increasing input such as [1,2,3] exposes missing flushes: its answer is 4, not merely its last height 3. Heights times widths can exceed 32-bit integers under the task limits; calculate in a sufficiently wide representation.

One push and one pop explain the linear bound

The inner loop may pop many indices on one iteration. Across the whole scan, each index is pushed once and popped at most once. Total pushes and pops are therefore at most 2n, giving O(n) time and O(n) auxiliary space. Counting the nested loops as O(n²) ignores that popped entries never return.

A sliding-window maximum uses the same dominance idea with a deque. Remove expired indices <= i-k from the front. Remove smaller or equal values from the back before adding i: a newer equal value expires later and is at least as good for all future windows containing the old one. The front is the maximum once a full window exists. Expiration is a separate condition from value dominance. This is transfer practice; the two implementations in this module use stacks.

Reconstruct and diagnose

1. For next-greater input [2,2,3,1], write the stack just before 3 arrives and finish the output. What wrong answer follows from popping on equality?
2. For histogram [3,3,2], the first pop at i=2 has width 1. Complete the next pop and final flush. Which bar owns the width-2 rectangle of height 3?
3. A window maximum implementation keeps values but no indices. On [5,1,1,1] with k=2, how can an old 5 survive beyond its window?

Check your reconstruction

1. Stack [0,1]; output [3,3,-1,-1]. An equality pop incorrectly assigns 2 as the answer at index 0 before seeing the actual next greater 3.
2. Pop index 0 next: width 2, area 6. At the end pop height 2 with width 3, also area 6. The earlier equal-height bar owns the full height-3 span.
3. Without its position or equivalent expiry tracking, the algorithm cannot tell that 5 left the window. Correct window maxima are [5,1,1].

Implement, then challenge the result with equal plateaus, all zeros, decreasing and increasing arrays. For small histograms, enumerate every contiguous range and calculate minimum height * width; this is an independent correctness oracle. Later change next-greater to next-greater-or-equal and derive the changed comparison before touching the code.