A brute-force approach to finding the next greater element for every item in an array checks every subsequent position, costing O(n squared) time. The monotonic stack eliminates that redundancy by maintaining a stack whose elements are always in sorted order - either strictly decreasing from bottom to top, or strictly increasing. This invariant lets you resolve "next greater" or "next smaller" queries in a single pass through the array with O(n) total time.

Monotonic Decreasing Stack

A monotonic decreasing stack keeps elements from bottom to top in decreasing order. When a new element arrives that is larger than the top of the stack, you pop. Every popped element has just found its next greater element - the new arrival. You keep popping until the stack is empty or the top is greater than or equal to the new element, then push the new element.

Walk through an example with [2, 1, 5, 6, 2, 3]:

1. Push 2. Stack: [2]
2. Push 1 (1 < 2, decreasing order holds). Stack: [2, 1]
3. Arrive at 5. Pop 1 - next greater of 1 is 5. Pop 2 - next greater of 2 is 5. Push 5. Stack: [5]
4. Arrive at 6. Pop 5 - next greater of 5 is 6. Push 6. Stack: [6]
5. Push 2. Stack: [6, 2]
6. Arrive at 3. Pop 2 - next greater of 2 is 3. Push 3. Stack: [6, 3]
7. Remaining elements (6, 3) have no next greater: answer is -1.

Monotonic Increasing Stack

A monotonic increasing stack keeps elements from bottom to top in increasing order. When a new element arrives that is smaller than the top, you pop. Every popped element has just found its next smaller element - the new arrival.

This is the mirror of the decreasing stack: swap "greater" with "smaller" and flip the comparison. The same O(n) guarantee applies because each element enters and leaves the stack at most once.

Why O(n) Total

The key insight that makes monotonic stacks efficient is that every element is pushed onto the stack exactly once and popped at most once. Across the entire array of n elements, the total number of push operations is n and the total number of pop operations is at most n. Even though a single arrival might trigger multiple pops, those pops are "charged" to the elements being popped - each of which was pushed earlier and will never be pushed again. The amortized cost per element is O(1), giving O(n) total.

The Stack as a Waiting List

Think of the stack as holding "unresolved" elements - elements that have not yet found their answer. Each element waits on the stack until a new arrival resolves it by being greater (or smaller) than it. Once resolved, the element is popped and never revisited. Unresolved elements at the end of the traversal receive a default answer (typically -1 or 0).

This mental model clarifies why the stack works: instead of looking forward from each element (brute force), you let future elements look backward and resolve everything they can in one shot.

The Next Greater Element I problem combines two techniques - a monotonic stack for computing next-greater relationships and a hash map for fast lookups. Given two arrays nums1 (a subset of nums2, with all unique elements), find for each element in nums1 its next greater element in nums2. If no next greater element exists, return -1.

Building the Next-Greater Map

The strategy is to ignore nums1 initially and build a complete next-greater mapping from nums2 alone. Process nums2 using a monotonic decreasing stack. Each time you pop an element, the current element is its next greater. Store this pair in a hash map.

1nums2 = [1, 3, 4, 2]
2
3Step 1: Push 1. Stack: [1]
4Step 2: Arrive 3. Pop 1 -> map[1] = 3. Push 3. Stack: [3]
5Step 3: Arrive 4. Pop 3 -> map[3] = 4. Push 4. Stack: [4]
6Step 4: Push 2 (2 < 4). Stack: [4, 2]
7End: 4 and 2 have no next greater -> map[4] = -1, map[2] = -1
8
9map = {1: 3, 3: 4, 4: -1, 2: -1}

Looking Up Results for nums1

Once the map is built, iterate through nums1 and look up each element. Since nums1 is a subset of nums2, every element in nums1 exists in the map.

nums1 = [4, 1, 2]
Results: [map[4], map[1], map[2]] = [-1, 3, -1]

Why Hash Map Plus Stack

Without the hash map, you would need to find each nums1 element's position in nums2 first (O(m) per element), then scan forward for the next greater (O(n) per element), giving O(m * n) total. The hash map reduces the lookup to O(1) per element. Building the map costs O(n) using the monotonic stack. Total: O(n + m) time, O(n) space.

Variations

This pattern extends to several related problems:

Next Greater Element II (circular array): Process the array twice (or use modular arithmetic) to simulate the circular wrap-around. The stack may hold elements from the "second pass" that resolve against elements from the "first pass."

Next Greater Element with duplicates: If elements can repeat, the hash map approach for NGE I breaks (duplicate keys). Instead, work directly with indices and build a result array indexed by position.

The Daily Temperatures problem shifts the monotonic stack pattern from finding next-greater values to finding next-greater distances. Given an array of daily temperatures, return an array where each position contains the number of days you must wait for a warmer temperature. If no warmer day exists, the answer is 0.

Why Store Indices, Not Values

In the Next Greater Element problem, you only need the value of the next greater element. Here, you need the distance to it - how many positions away is the next warmer day. Storing the temperature value on the stack tells you "the answer exists" but not "how far away is it." Storing the index lets you compute the distance: current_index - stack_top_index.

This is the most important adaptation to internalize: when a problem asks about distance, position, or count between elements, store indices on the stack and use the original array to look up values.

Algorithm Walkthrough

Given temperatures [73, 74, 75, 71, 69, 72, 76, 73]:

1. Push index 0 (temp 73). Stack: [0]
2. Index 1 (temp 74 > 73). Pop 0, result[0] = 1 - 0 = 1. Push 1. Stack: [1]
3. Index 2 (temp 75 > 74). Pop 1, result[1] = 2 - 1 = 1. Push 2. Stack: [2]
4. Index 3 (temp 71 < 75). Push 3. Stack: [2, 3]
5. Index 4 (temp 69 < 71). Push 4. Stack: [2, 3, 4]
6. Index 5 (temp 72). Pop 4, result[4] = 5 - 4 = 1. Pop 3, result[3] = 5 - 3 = 2. 72 < 75, stop. Push 5. Stack: [2, 5]
7. Index 6 (temp 76). Pop 5, result[5] = 6 - 5 = 1. Pop 2, result[2] = 6 - 2 = 4. Push 6. Stack: [6]
8. Index 7 (temp 73 < 76). Push 7. Stack: [6, 7]
9. Remaining indices 6 and 7 get result 0 (no warmer day).

Result: [1, 1, 4, 2, 1, 1, 0, 0]

Connecting to the Monotonic Stack Pattern

The stack holds indices of temperatures in decreasing order of their values. This is exactly a monotonic decreasing stack, just indexed. The invariant: for any two indices i and j on the stack where i is below j, temperatures[i] >= temperatures[j]. A new index k with temperatures[k] > temperatures[stack_top] breaks this invariant, triggering pops.

Every pop answers the question for the popped index. Every remaining element at the end has no answer (result stays 0, the initialized default).

Implementation Note

Initialize the result array with zeros. This way, elements that are never popped (no warmer day exists) already have the correct answer without explicit handling after the traversal.

The monotonic stack reaches its most powerful applications in two classic problems: Largest Rectangle in Histogram and Trapping Rain Water. Both require finding boundaries on both sides of each element - a pattern that monotonic stacks handle elegantly.

Largest Rectangle in Histogram

Given an array of bar heights, find the area of the largest rectangle that fits entirely under the histogram. For each bar, the largest rectangle using that bar's height extends from the nearest shorter bar on the left to the nearest shorter bar on the right.

The key observation: for a bar at position i with height h[i], the widest rectangle of height h[i] extends from the first bar shorter than h[i] on the left (call its position left_boundary) to the first bar shorter than h[i] on the right (call its position right_boundary). The width is right_boundary - left_boundary - 1.

Using a monotonic increasing stack:

Maintain a stack of indices where the corresponding heights are in increasing order from bottom to top. When a new bar is shorter than the stack's top, the top bar has found its right boundary (the new bar) and its left boundary (the element below it on the stack, or -1 if the stack is empty after popping).

Walk through [2, 1, 5, 6, 2, 3]:

1. Push 0 (height 2). Stack: [0]
2. Index 1 (height 1 < 2). Pop 0: height = 2, right = 1, left = -1, width = 1-(-1)-1 = 1, area = 2. Push 1. Stack: [1]
3. Push 2 (height 5). Stack: [1, 2]
4. Push 3 (height 6). Stack: [1, 2, 3]
5. Index 4 (height 2 < 6). Pop 3: height = 6, right = 4, left = 2, width = 4-2-1 = 1, area = 6. Pop 2: height = 5, right = 4, left = 1, width = 4-1-1 = 2, area = 10. 2 >= 2? No (using strict less-than for pop). Push 4. Stack: [1, 4]
6. Push 5 (height 3). Stack: [1, 4, 5]
7. End: drain stack. Pop 5: height = 3, right = 6, left = 4, width = 6-4-1 = 1, area = 3. Pop 4: height = 2, right = 6, left = 1, width = 6-1-1 = 4, area = 8. Pop 1: height = 1, right = 6, left = -1, width = 6-(-1)-1 = 6, area = 6.

Maximum area = 10, from the rectangle spanning bars at indices 2-3 with height 5.

Trapping Rain Water

Given an elevation map (array of non-negative integers representing bar heights), calculate how much rain water can be trapped between the bars.

Stack-based approach: Use a monotonic decreasing stack. When a taller bar arrives (breaking the decreasing invariant), water can be trapped between the current bar and the bar below the popped element on the stack. The popped element is the "bottom" of the water container.

For each pop:

• The popped bar is the bottom of the trapped water.
• The current bar is the right wall.
• The new stack top (after popping) is the left wall.
• Water height = min(left wall height, right wall height) - bottom height.
• Water width = current index - left wall index - 1.
• Trapped water for this layer = height * width.

Walk through [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

The stack processes bars left to right. Whenever a bar is taller than the top, it pops and calculates trapped water layer by layer. Index 3 (height 2) traps water over the valley at index 2. Index 7 (height 3) traps water over the valley spanning indices 4-6. The total trapped water is 6.

Alternative: Two-Pointer Approach

Trapping rain water can also be solved with two pointers - left and right - moving inward. At each step, the side with the shorter bar moves inward. The water at each position equals min(max_left, max_right) - height[i]. This approach uses O(1) space compared to the stack's O(n), but the stack-based approach generalizes better to related problems (like the histogram problem) because it explicitly tracks boundaries.

Connecting the Two Problems

Both problems use monotonic stacks to find boundaries, but with opposite orientations:

• Histogram: Increasing stack. A shorter bar triggers pops, because the tall bar can no longer extend. Computes width * height for rectangles.
• Trapping water: Decreasing stack. A taller bar triggers pops, because water can now be trapped above the popped bar. Computes layer-by-layer water volumes.

Understanding this duality - same data structure, opposite invariant, opposite trigger - is the key to mastering monotonic stack problems.