Monotonic Stack

Maintain a stack that is always increasing or decreasing, popping elements that violate the invariant — enables O(n) solutions for 'next greater/smaller element' problems.

When to use it

Next greater/smaller element to the right or left.
Largest rectangle in histogram, daily temperatures, trapping rain water.

Signals in the problem statement

Need to find the nearest larger/smaller element for every position.
Brute force would be O(n²) nested loop.

Common pitfalls

Confusing monotonic increasing vs decreasing stack (store indices or values?).
Not realizing you can traverse right-to-left or left-to-right depending on which 'next' direction you need.

Practice Problems

Daily Temperatures

Medium

Asked at: Amazon, Bloomberg, Meta

Practiced

Given an array of daily temperatures, return an array where answer[i] is the number of days until a warmer temperature. If none, answer[i] = 0.

Time: O(n) · Space: O(n)

Largest Rectangle in Histogram

Hard

Asked at: Amazon, Google, Meta

Practiced

Given an array of integers representing histogram bar heights (width 1 each), find the area of the largest rectangle in the histogram.

Time: O(n) · Space: O(n)