Monotonic Stack

Core Concepts

Monotonic Stack — a stack where elements are maintained in strictly monotonically increasing or decreasing order from bottom to top at all times. Achieving this requires popping elements that violate the order before pushing a new one; the popped elements are the answer for those indices.

Nearest Smaller / Larger Element — the canonical problem class solved by monotonic stack. For each element, find the closest element to its left or right that is smaller (or larger). The stack naturally surfaces these relationships during the pop phase.

Span / Width — the distance or index range over which an element is the dominant (min or max) value. Problems asking for widths, areas, or subarray boundaries frequently reduce to finding nearest-smaller/larger boundaries.

Next Greater Element (NGE) — for each index i, the first index j > i such that arr[j] > arr[i]. Computed in one pass using a decreasing stack.

Previous Smaller Element (PSE) — for each index i, the last index j < i such that arr[j] < arr[i]. Computed in one pass using an increasing stack.

Online vs. Offline — monotonic stack solves queries offline (all elements known upfront) in O(n). For online (streaming) queries with arbitrary range constraints, segment trees or sparse tables are needed instead.

---

Structural Invariants

---

Internal Representation

Array-backed stack (Python list) — the only representation used in practice. stack.append(i) and stack.pop() are O(1) amortised. No pointer overhead.

Index storage vs. value storage — almost always store the index, not the value. Span and distance calculations require indices; values are retrieved as arr[stack[-1]]. Storing values alone is only valid when distances are irrelevant.

Auxiliary result arrays — typically allocate left[n] and right[n] arrays initialised to sentinel values (-1, n, or 0). These are filled during the pop phase: when index i causes index j to be popped, right[j] = i (i is the next-greater/smaller for j).

Two-pass vs. one-pass — left boundaries (PSE/PGE) are computed in a left-to-right pass; right boundaries (NSE/NGE) in a left-to-right pass as well (using the pop event to assign right[popped] = current). Both passes can sometimes be fused, but separating them reduces bugs.

---

Types / Variants

Choosing strict vs. non-strict: use strict when equal values must be treated as transparent (the boundary must be strictly larger/smaller). Use non-strict when equal values act as the answer. Most LeetCode problems use strict.

---

Topic-Specific Operations

Push with Pop-While-Invariant-Breaks

Core operation. Before pushing index i, pop all stack elements whose values violate the invariant with arr[i].

while stack and arr[stack[-1]] < arr[i]:  # example: decreasing stack
    j = stack.pop()
    right[j] = i   # arr[i] is the next-greater for arr[j]
stack.append(i)

Time: O(1) amortised per element (each element pushed and popped at most once). Space: O(n) worst case (sorted input).

Reading the Stack for Left Boundary

After the pop-while loop, the stack top (if non-empty) is the nearest element to the left that satisfies the invariant. If the stack is empty, no such element exists (use sentinel −1 or 0).

left[i] = stack[-1] if stack else -1

Draining the Remaining Stack

After the full array traversal, elements still in the stack have no valid right boundary. Assign sentinel values (n for index-based, 0 for spans).

while stack:
    right[stack.pop()] = n   # no NGE exists → use n as sentinel

Two-Pointer Boundary Merge

Once left[i] and right[i] are computed, the "width dominated by element i" is right[i] - left[i] - 1. Used directly in area/span computations.

---

Key Algorithms

Next Greater Element (single array)

For each index, find the first index to the right with a larger value. Uses a decreasing stack. When arr[i] > arr[stack[-1]], the top is popped and assigned NGE = i.

Time O(n), Space O(n). Each element enters and leaves the stack exactly once.

Previous Smaller Element

Process left to right using an increasing stack. Before pushing i, the current stack top (after draining violators) is left[i].

Time O(n), Space O(n).

Stock Span Problem

For each day, count how many consecutive previous days had price ≤ today's price. Span = i - left[i] where left[i] is PSE's index (or −1).

Time O(n), Space O(n).

Largest Rectangle in Histogram

For each bar, find the maximal rectangle with height = bar's height. Width = right[i] - left[i] - 1 (PSE on both sides). Answer = max over all bars of height[i] * width.

Time O(n), Space O(n). A common O(n²) mistake is recomputing widths naively.

Trapping Rain Water (stack approach)

Use a decreasing stack. When a taller bar is found, the popped bar is the bottom of a water pocket; left wall = new stack top, right wall = current bar. Contribution = min(left_height, right_height) - bottom_height) * width.

Time O(n), Space O(n). (Two-pointer version is O(1) space but harder to generalise.)

Sum of Subarray Minimums / Maximums

For each element, compute how many subarrays it is the minimum of: (i - left[i]) * (right[i] - i). Sum all contributions.

Key subtlety: handle duplicates by using strict inequality on one side and non-strict on the other to avoid double-counting.

Time O(n), Space O(n).

Largest Rectangle in Binary Matrix

For each row, compute histogram heights (consecutive 1s above including current row). Apply Largest Rectangle in Histogram per row.

Time O(m·n), Space O(n).

Remove K Digits (greedy monotonic stack)

Build an increasing stack of digits. When a digit smaller than the stack top arrives and k > 0, pop (remove) the top, decrement k. Result is the stack after processing.

while stack and k and stack[-1] > d:
    stack.pop(); k -= 1
stack.append(d)

Time O(n), Space O(n).

Daily Temperatures

Classic NGE variant: answer[i] = distance to next warmer day. Pop when T[i] > T[stack[-1]]; answer[popped] = i - popped.

Time O(n), Space O(n).

---

Advanced Techniques

Monotonic Stack + Contribution Counting

Solves: problems asking for the sum (or count) of min/max values over all subarrays or subsets.

Mechanism: for each element, the two monotonic stacks (PSE and NSE) define the exact set of subarrays where the element is the minimum. The count of such subarrays = (i - left[i]) * (right[i] - i). Multiply by value and sum.

When to prefer over brute force: any subarray aggregate (sum of mins, sum of maxes) over n > 1000. Brute force is O(n²) or O(n³); this is O(n).

Duplicate handling: use strict on one side (PSE uses <, NSE uses <=) to partition subarrays with duplicate minimums without overlap. Getting this wrong produces overcounting.

Time O(n), Space O(n).

Monotonic Stack + Sliding Window Maximum (Monotonic Deque)

Solves: maximum (or minimum) in every window of fixed size k; queries over a moving range.

Mechanism: use a double-ended queue (deque) rather than a plain stack, maintaining a decreasing deque of indices. Expire the front when it falls outside the window; pop the back when the new element is larger. Front = window maximum.

When to prefer over segment tree: fixed window size; no point updates needed. Segment tree/sparse table handles arbitrary range max queries; deque handles only sliding fixed-size windows.

See sliding-window.md for full deque-based sliding window coverage.

Time O(n), Space O(k).

Monotonic Stack for 2D Problems (Histogram Extension)

Solves: maximal rectangle, maximal square area in binary grids; problems reducible to per-row histogram.

Mechanism: convert each row to a height array (increment on 1, reset on 0), then run the 1D histogram algorithm. Effectively runs n independent monotonic stack sweeps.

When to prefer over DP: when the problem is a max-area rectangle (not max-square; max-square uses DP more cleanly). Both are O(m·n) but the stack approach generalises to non-rectangular shapes in some variants.

Time O(m·n), Space O(n).

Monotonic Stack for Lexicographically Smallest / Largest Result

Solves: remove k digits, build smallest number from string after deletions, create non-decreasing subsequence of length k.

Mechanism: greedily maintain an increasing (for smallest result) or decreasing (for largest result) stack of characters/digits. Pop when current element improves the stack ordering and budget remains.

When to prefer over sorting: the output must preserve relative order from the input. Sorting destroys order; this greedy preserves it.

Time O(n), Space O(n).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Storing values instead of indices: a common beginner mistake. When only the value is stored, span and distance calculations (right[i] - left[i] - 1) are impossible. Always store indices; retrieve values as arr[stack[-1]].

• Off-by-one in width calculation: width of the rectangle dominated by bar i is right[i] - left[i] - 1, not right[i] - left[i]. The boundaries are exclusive. Forgetting the −1 inflates the area by the height of the bar.

• Duplicate values causing double-counting in contribution problems: if PSE uses < and NSE also uses <, a subarray whose minimum appears at two positions is counted twice. Fix: use < on one side and <= on the other to break the tie consistently.

• Empty stack access: reading stack[-1] on an empty list raises IndexError. Use a sentinel push (index −1 with a guard value) or an explicit if stack check before every top-read.

• Circular arrays without doubling: naively running one pass on a circular array misses elements whose NGE wraps around. The fix is iterating over indices 0 to 2n−1 modulo n, pushing only when i < n.

• Wrong stack direction: using an increasing stack when you need NSE (should use decreasing) produces the wrong boundary. Mnemonic: decreasing stack → pop when current is larger → pop event reveals NGE; increasing stack → pop when current is smaller → pop event reveals NSE.

• Not draining after the loop: elements remaining in the stack after the traversal have no valid right boundary. Failing to drain them leaves their right[] entries uninitialised (or at default 0), producing incorrect widths and areas.

• Modifying the input array for histogram rows: in matrix rectangle problems, a fresh height array per row avoids corrupting the original grid, but the heights must be reset to 0 (not carried over) whenever a 0 is encountered in the current row.

• Stack holding stale indices in sliding window variant (deque): in the monotonic deque pattern, indices outside the window must be expired from the front before reading the maximum. Forgetting this returns maximums from outside the current window.

---

Implementation Notes

• Python list is the correct stack; collections.deque is needed only for the sliding-window (deque) variant where O(1) popleft is required.
• Python has no stack overflow concern for iterative monotonic stacks, but a recursive implementation of any O(n)-depth traversal will hit the default recursion limit of 1000; avoid recursion entirely.
• float('inf') and float('-inf') are valid sentinels for guard values but slightly slower than using integer bounds (10**9); in competitive settings use integer sentinels.
• The while stack and condition idiom short-circuits correctly in Python — the empty-stack check must come first; reversing the order causes an IndexError.
• When computing areas with height × width, ensure both are integers before multiplication; Python handles big integers natively so overflow is not a concern, but mixing float heights (from sentinel initialisation) can cause precision issues.
• In problems like "Sum of Subarray Minimums," the answer can exceed 32-bit integer range; always apply modulo (% (10**9 + 7)) at each addition step, not just at the end, to prevent TLE from big-integer arithmetic.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Foundational (Next Greater / Smaller)

• Daily Temperatures (LC 739) — NGE with distance
• Next Greater Element I (LC 496) — basic NGE with a hashmap result
• Next Greater Element II (LC 503) — circular NGE
• Online Stock Span (LC 901) — incremental span; stack persists across calls

Area and Span

• Largest Rectangle in Histogram (LC 84) — dual-boundary merge; gold-standard problem for this topic
• Maximal Rectangle (LC 85) — histogram extension to 2D binary matrix
• Trapping Rain Water (LC 42) — decreasing stack; water pocket on pop

Subarray Aggregates

• Sum of Subarray Minimums (LC 907) — contribution counting with duplicate handling
• Sum of Subarray Ranges (LC 2104) — sum of (max − min) per subarray; two monotonic stacks
• Number of Visible People in a Queue (LC 1944)

Lexicographic Greedy

• Remove K Digits (LC 402) — smallest number after removing k digits
• Create Maximum Number (LC 321) — hard; combines two greedy stacks with a merge
• 132 Pattern (LC 456) — decreasing stack scanning right to left

Hard / Combined

• Maximum Width Ramp (LC 962)
• Minimum Number of Increments on Subarrays (LC 1526)
• Count of Submatrices That Sum to Target — combines prefix sum + histogram reduction

Clarification Questions to Ask

• Are there duplicate values? (affects strict vs non-strict invariant choice)
• Is the array circular? (affects whether double-pass is needed)
• Is "larger" strictly greater, or greater-or-equal? (determines which side uses strict inequality)
• What is the expected output — index, value, or distance?
• Are there negative values? (sentinel choice: −1 may be a valid index; use a flag or float('-inf'))
• For matrix problems: can rows contain values other than 0 and 1, or are heights given directly?

Common Interview Mistakes

• Using a decreasing stack when the problem needs an increasing stack (or vice versa), producing the wrong boundary direction.
• Forgetting to drain the remaining stack after the traversal, leaving sentinel entries uninitialised.
• Storing values instead of indices in the stack, making span calculation impossible.
• Off-by-one in the width formula: writing right[i] - left[i] instead of right[i] - left[i] - 1.
• Not handling duplicates in Sum of Subarray Minimums, leading to double-counting and a wrong answer.
• Ignoring the modular arithmetic requirement in aggregate problems, causing TLE or wrong answer on large inputs.
• In the circular NGE variant, pushing indices >= n into the result array rather than guarding with i < n.

Typical Follow-Up Escalations

• "Can you solve Trapping Rain Water in O(1) space?" → Two-pointer approach; maintain left_max and right_max pointers advancing inward.
• "What if the histogram bars have floating-point heights?" → Algorithm is identical; replace integer sentinels with float('-inf').
• "Can you make Stock Span work online (one query at a time)?" → Yes — the stack persists between calls; exactly what LC 901 tests.
• "Sum of subarray minimums, but now for all contiguous subarrays of length exactly k?" → Slide a window of size k; combine monotonic deque for range min with a running sum.
• "Largest rectangle, but the grid has obstacles (not just 0/1)?" → Treat obstacle rows as height-reset boundaries; run histogram per row with modified height accumulation.
• "What is the time complexity if the array is already sorted?" → Still O(n) for the stack; each element is pushed once and popped at most once regardless of input order.