iii. Monotonic Stack

A stack kept sorted answers “nearest element to the left/right that is smaller/greater” for every position in $O(n)$ total. It is also the Cartesian tree in disguise, which explains why it shows up in RMQ, histograms and “sum over all subarrays” problems.

Nearest smaller / greater

vector<int> L(n), R(n), st;                    // L: previous strictly smaller, R: next smaller-or-equal
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] >= a[i]) R[st.back()] = i, st.pop_back();
    L[i] = st.empty() ? -1 : st.back();
    st.push_back(i);
}
for (int i : st) R[i] = n;

One pass gives both sides: an index is popped by its next smaller-or-equal element, and when pushed it reads its previous strictly smaller one. Flip the comparisons for “greater”. In general: for “previous”, read st.back() before pushing the current index; for “next”, assign the answer while popping.

Want	Direction	Pop while
previous smaller	left to right	a[st.back()] >= a[i]
previous greater	left to right	a[st.back()] <= a[i]
next smaller	right to left (or one pass, as above)	a[st.back()] >= a[i]
next greater	right to left (or one pass)	a[st.back()] <= a[i]

Ties: strict on one side and non-strict on the other means every subarray has exactly one designated minimum (the leftmost or rightmost occurrence). With strict on both sides, equal elements double count.

Proof: the one-pass stack is correct and $O(n)$

Invariant. After processing index $i$ (before the next iteration), the stack holds, bottom to top, exactly the indices $j\le i$ whose value has not yet been exceeded or matched by anything to their right so far — equivalently, a strictly increasing subsequence of values (since anything $\ge a[i]$ already got popped when $i$ arrived). Why L[i] is correct: at the moment $i$ is pushed, every index already popped (by $i$ or earlier) had value $\ge$ the value that popped it, so it cannot be $i$‘s previous-smaller; the stack top at that instant is therefore the nearest index to the left whose value is strictly less than $a[i]$ — exactly L[i]. Why R[st.back()] is correct when $i$ pops it: $i$ is the first index encountered (scanning left to right) with $a[i]\le a[\text{popped}]$, since every index between the popped one and $i$ was itself $>a[\text{popped}]$ (else it would have popped it first) — so $i$ is the next smaller-or-equal. Complexity: each index is pushed exactly once and popped at most once, so the while loop runs at most $n$ times in total across the whole scan, giving $O(n)$. $■$

Contribution: sums over all subarrays

$a_i$ is the minimum of $(i-L_i)(R_i-i)$ subarrays:

${\sum }_{\text{subarrays}}\min ={\sum }_i{a}_i(i-L_i)(R_i-i).$

Proof: the contribution formula

A subarray $[l,r]$ (with $l\le i\le r$) has $a_i$ as its minimum (under the tie-breaking convention above, which guarantees a unique witness index per subarray) iff every element in $[l,i)$ is $>a_i$ and every element in $(i,r]$ is $\ge a_i$ (or the strict/non-strict sides matching whichever convention was fixed) — i.e. iff $l\in (L_i,i]$ and $r\in [i,R_i)$, since $L_i$ is the nearest index with a smaller-or-not-dominated value and $R_i$ the nearest with a value that would break the minimum. These two ranges are independent, giving $(i-L_i)$ choices for $l$ and $(R_i-i)$ for $r$, so $a_i$ is the designated minimum of exactly $(i-L_i)(R_i-i)$ subarrays. Since every subarray has exactly one designated minimum (by the tie-breaking rule), summing $a_i$ times its count over all $i$ counts every subarray’s minimum exactly once, proving ${\sum }_{\text{subarrays}}\min ={\sum }_i{a}_i(i-L_i)(R_i-i)$. $■$

• Sum of ranges ($\max -\min$): the maximum version minus the minimum version.
• Count subarrays where $a_i$ is the max and the subarray satisfies something else (for example length $\ge k$, or sum constraints): the range of valid $(l,r)$ is the rectangle $(L_i,i]\times [i,R_i)$, so count it with arithmetic or with small-to-large over the shorter side (iterating the shorter side gives $O(n\log n)$ total, the “divide at the maximum” trick).
• Sum of gcds or ANDs over all subarrays: the set of distinct values ending at $r$ has size $O(\log V)$ (Subarray Aggregates).

Largest rectangle in a histogram

The best rectangle with bar $i$ as its shortest spans $(L_i,R_i)$, so the answer is ${\max }_i{h}_i(R_i-L_i-1)$. In one pass, with a sentinel:

Proof: the histogram formula and its one-pass computation

Formula. Fix $i$ and consider the rectangle of height $h_i$ that is as wide as possible while staying inside the histogram. It can extend left until hitting a bar shorter than $h_i$ (at $L_i$) and right until hitting one shorter (at $R_i$), so its width is $R_i-L_i-1$ and its area $h_i(R_i-L_i-1)$. Every candidate optimal rectangle has some bar as its shortest (the rectangle’s height is the min height over its span), and for that bar $i$, the rectangle must lie within $(L_i,R_i)$ — so it is no larger than the maximal rectangle with bar $i$ as the limiting height. Hence the true optimum equals ${\max }_i{h}_i(R_i-L_i-1)$. One-pass correctness. When $i$ pops bar $t$ off the stack (because $h[i]\le h[t]$), every bar between $t$ and $i$ was $>h[t]$ (else it would have popped $t$ first), so $i$ is exactly $R_t$; and the new stack top after popping $t$ is the nearest remaining bar with height $<h[t]$ scanning left — exactly $L_t$ — since everything between it and $t$ was $\ge h[t]$ and already popped. So both boundaries of $t$‘s maximal rectangle are known at the instant of popping, letting the single pass compute $h_t\cdot (i-\text{newtop}-1)$ correctly for every $t$; the sentinel $-1$ height forces every remaining bar to pop and be accounted for. $■$

Tested against an $O(n^2)$ brute force (for each bar, extend both directions linearly) on random height arrays.

ll largestRectangle(vector<ll> h) {
    h.push_back(-1); vector<int> st; ll best = 0;
    for (int i = 0; i < sz(h); i++) {
        while (!st.empty() && h[st.back()] >= h[i]) {
            ll ht = h[st.back()]; st.pop_back();
            int left = st.empty() ? -1 : st.back();
            best = max(best, ht * (i - left - 1));
        }
        st.push_back(i);
    }
    return best;
}

Maximal all-ones rectangle in a grid: for each row, heights = consecutive ones ending at that row; run the histogram per row, $O(nm)$. Count all-ones subrectangles: per row, the number of rectangles with bottom-right corner at $(i,j)$ satisfies $c_j=c_{L_j}+h_j(j-L_j)$ where $L_j$ is the previous strictly smaller height. $O(nm)$ in total.

Divide-and-conquer alternative: find the minimum bar; the answer either spans the whole range at that height or lies entirely to one side. With a sparse table for the minimum’s index this is $O(n\log n)$, and $O(n)$ if the Cartesian tree below is built first, since the recursion is that tree — slower to set up than the stack, but it’s the clearest explanation of why the Cartesian tree and the monotonic stack solve the same problem.

Trapping rain water

Water at $i$ is $\min ({\max }_{j\le i}{h}_j,{\max }_{j\ge i}{h}_j)-h_i$. Two pointers: move the side with the smaller current height, since its running maximum is the binding wall.

Proof: moving the shorter side is safe

Let $lm={\max }_{j\le l}{h}_j$ and $rm={\max }_{j\ge r}{h}_j$ be the code’s running maxima (each includes the current pointer’s own bar once absorbed), and let $\text{maxright}(l)={\max }_{j\ge l}{h}_j$ be the true right maximum at position $l$ — the quantity the water formula needs but the algorithm never computes directly. Invariant: whenever $l<r$, $lm\le {\max }_{l\le j\le r}{h}_j$ and $rm\le {\max }_{l\le j\le r}{h}_j$. Base case ($l=0,r=n-1$, both maxima $0$): trivial. Inductive step, moving $l$ (case $h[l]<h[r]$): the new $l{m}^{\prime }=\max (lm,h[l])\le {\max }_{l\le j\le r}{h}_j$ since both $lm$ (by hypothesis) and $h[l]$ are at most that range’s max. The window shrinks to $[l+1,r]$; if ${\max }_{l+1\le j\le r}{h}_j\ge h[l]$ then ${\max }_{l\le j\le r}{h}_j={\max }_{l+1\le j\le r}{h}_j$, so $l{m}^{\prime }$ stays within the new, smaller range’s max. The only risk is ${\max }_{l+1\le j\le r}{h}_j<h[l]$ — but $r\ge l+1$ puts $h[r]$ inside that range, so it would force $h[r]<h[l]$, contradicting the case hypothesis $h[l]<h[r]$. So the invariant persists; the symmetric argument covers moving $r$. Conclusion: right before adding water at $l$ (when $h[l]<h[r]$), the invariant gives $lm\le {\max }_{l\le j\le r}{h}_j\le \text{maxright}(l)$, so $\min (lm,\text{maxright}(l))=lm$ regardless of the true (unknown to the algorithm) value of $\text{maxright}(l)$ — the water formula reduces to $lm-h[l]$, exactly what the code adds, with no need to ever learn $\text{maxright}(l)$. $■$

ll trap(const vector<int>& h) {
    int l = 0, r = sz(h) - 1, lm = 0, rm = 0; ll w = 0;
    while (l < r)
        if (h[l] < h[r]) lm = max(lm, h[l]), w += lm - h[l++];
        else rm = max(rm, h[r]), w += rm - h[r--];
    return w;
}

The stack version fills horizontal layers: pop a bottom, and the water above it is bounded by the new top and the current bar. 2D version: push all border cells into a min-heap and flood inward Dijkstra-style, since water on a grid escapes over the lowest point of the boundary. The current level is $\max (\text{level},h)$, and each cell traps $\text{level}-h$. $O(nm\log (nm))$ — the “water level” propagates inward exactly as Dijkstra’s distances do.

Method	Time	Space	Note
brute force (max on each side per $i$)	$O(n^2)$	$O(1)$	the starting point
prefix/suffix maxima	$O(n)$	$O(n)$	clearest
two pointers	$O(n)$	$O(1)$	optimal
monotonic stack	$O(n)$	$O(n)$	layer decomposition

Variant	Method
2D trapping rain water	priority queue from the border inward (Dijkstra-like flood)
container with most water	two pointers on $\min (h_l,h_r)\times (r-l)$
largest rectangle in a histogram	monotonic stack, see above
water with a leak / drainage	modify the boundary condition
maximum water after removing $k$ bars	harder; DP or greedy depending on the constraints

Cartesian tree

The min-Cartesian tree of $a$ has the minimum at the root, the left part as the left subtree and the right part as the right subtree. The monotonic stack is its right spine during construction:

vector<int> par(n, -1), st;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!st.empty() && a[st.back()] > a[i]) last = st.back(), st.pop_back();
    if (last != -1) par[last] = i;
    if (!st.empty()) par[i] = st.back();
    st.push_back(i);
}

Proof: the stack construction builds the Cartesian tree

The stack always holds, bottom to top, the right spine of the tree built from $a[\mathrm{0..}i)$ so far (the path from the root following only rightmost children), with values increasing bottom to top — this holds inductively since the spine’s values must increase downward for the min-heap property to hold along a chain of right-children. When $i$ arrives, every stack entry with value $>a[i]$ must move below $i$ in the final tree (min-heap property), and they are popped from the top of the stack down, i.e. from the shallowest spine node down to the deepest one still exceeding $a[i]$ — call the last one popped last. Re-rooting that whole popped chain at $i$ as a single left subtree is correct because last previously had no right child (it was the bottom of the old spine), so attaching par[last]=i slots $i$ above exactly that chain, preserving both the heap property (every popped value $>a[i]$) and the BST property (every popped index $<i$, since the stack only ever holds indices in increasing left-to-right order). After popping, if the stack is non-empty its top has the first remaining value $<a[i]$ and necessarily a larger index than any popped node but still $<i$, so attaching $i$ as its right child (par[i]=st.back()) extends the spine correctly; pushing $i$ then makes it the new spine bottom. Induction on $i$ shows this reconstructs the heap-by-value, BST-by-index Cartesian tree exactly, and since each index is pushed once and popped at most once, the construction is $O(n)$. $■$

• $\mathrm{RMQ}(l,r)=\mathrm{LCA}(l,r)$ in the Cartesian tree, giving the $O(n)$/$O(1)$ RMQ (RMQ).
• “Divide at the minimum” recursions are traversals of this tree. Merging the smaller child into the larger gives $O(n\log n)$ for many “count subarrays whose minimum (or maximum) satisfies $X$” problems.
• A treap is a Cartesian tree on (key, random priority).

More stack patterns

Problem	Idea
stock span, days until warmer	previous/next greater, distance
lexicographically smallest subsequence of length $k$ / remove $k$ digits	pop while the top is larger and enough elements remain
smallest subsequence containing every distinct letter once	pop while top > current and the top occurs later
circular next greater	iterate $2n$ positions, push only in the first pass
visible people in a queue / count pairs that see each other	pop smaller, count pops, handle equal heights with counts
sum of $\max -\min$ of all subarrays	two stacks, contribution
convex hull (monotone chain), CHT with sorted slopes	same pop-while-bad discipline with a cross product
matching brackets, longest valid parentheses	stack of indices with a sentinel base
next greater for queries offline / on trees	stack along the DFS path with rollback

Debugging

The stack holds exactly the indices still “open”, whose answer hasn’t been determined. If a result is wrong, print the stack after each step on a 6-element example. Nearly every bug is < versus <=, or reading the top after pushing instead of before.