Monotonic Stack Data Structure Tutorial

What Is a Monotonic Stack?

A monotonic stack is a stack-based technique in which elements are maintained in a specific increasing or decreasing order. It is commonly used to solve problems that ask for the next greater element, next smaller element, previous greater element, or previous smaller element.

The important idea is that elements that can no longer be useful for answering future queries are removed from the stack. This allows many problems that appear to require nested loops to be solved in linear O(n) time.

Core idea

Maintain a stack whose values follow a required order. Before adding a new element, remove stack elements that violate that order.

Why Use a Monotonic Stack?

Consider the problem of finding the next greater element for every value in an array. A straightforward solution could compare every element with all elements to its right. In the worst case, this requires O(n²) time.

A monotonic stack avoids repeatedly comparing elements that have already been resolved or eliminated. Each element is pushed onto the stack once and removed at most once, resulting in an overall O(n) solution.

Types of Monotonic Stacks

The two main forms are based on the order maintained inside the stack.

Type	Stack Property	Common Use
Monotonic Increasing	Values remain increasing from bottom to top	Next smaller element patterns
Monotonic Decreasing	Values remain decreasing from bottom to top	Next greater element patterns

The exact choice depends on the relationship the problem asks you to find. It is often easier to decide which stack to use by focusing on what should happen when the current element is compared with the stack's top element.

Monotonic Decreasing Stack

A monotonic decreasing stack keeps values in decreasing order from the bottom toward the top. This pattern is commonly used when looking for the next greater element.

Suppose the input is:

[2, 1, 2, 4, 3]

When a larger value arrives, elements smaller than the current value can be resolved because the current value is their next greater element.

Next Greater Element

The next greater element for an element is the first element to its right that is greater than it. If no such element exists, the result is usually represented by -1.

For example:

Input:
[2, 1, 2, 4, 3]

Output:
[4, 2, 4, -1, -1]

For the first value, 2, the next greater value is 4. For 1, it is 2. The value 4 has no greater element to its right.

Solving Next Greater Element with a Stack

One useful approach is to traverse the array from right to left. The stack stores candidates that may be the next greater element for values encountered later.

Start from the rightmost element.
Remove stack elements that are smaller than or equal to the current value.
The remaining stack top, if present, is the next greater element.
Push the current value onto the stack.
Continue toward the beginning of the array.

const numbers = [2, 1, 2, 4, 3];
const result = new Array(numbers.length).fill(-1);
const stack = [];

for (let i = numbers.length - 1; i >= 0; i--) {
  while (
    stack.length > 0 &&
    stack[stack.length - 1] <= numbers[i]
  ) {
    stack.pop();
  }

  if (stack.length > 0) {
    result[i] = stack[stack.length - 1];
  }

  stack.push(numbers[i]);
}

console.log(result);
// [4, 2, 4, -1, -1]

How the Stack Changes

Understanding the stack state is often more useful than memorizing the code. For the array [2, 1, 2, 4, 3], the algorithm processes values from right to left.

Current	Action	Result
3	No greater candidate	-1
4	Remove 3	-1
2	4 is greater	4
1	2 is greater	2
2	Remove 1, then find 4	4

Next Smaller Element

The same technique can be reversed to find the first smaller element to the right. In this case, elements that are greater than or equal to the current value can be removed from the stack.

const numbers = [4, 5, 2, 10, 8];

const result = new Array(numbers.length).fill(-1);
const stack = [];

for (let i = numbers.length - 1; i >= 0; i--) {
  while (
    stack.length > 0 &&
    stack[stack.length - 1] >= numbers[i]
  ) {
    stack.pop();
  }

  if (stack.length > 0) {
    result[i] = stack[stack.length - 1];
  }

  stack.push(numbers[i]);
}

console.log(result);
// [2, 2, -1, 8, -1]

Previous Greater Element

Monotonic stacks can also solve problems involving elements to the left of the current position. For a previous greater element, the array can be processed from left to right while maintaining a suitable decreasing stack.

const numbers = [10, 4, 2, 20, 40, 12, 30];

const result = new Array(numbers.length).fill(-1);
const stack = [];

for (let i = 0; i < numbers.length; i++) {
  while (
    stack.length > 0 &&
    stack[stack.length - 1] <= numbers[i]
  ) {
    stack.pop();
  }

  if (stack.length > 0) {
    result[i] = stack[stack.length - 1];
  }

  stack.push(numbers[i]);
}

console.log(result);

Previous Smaller Element

Similarly, a monotonic stack can identify the closest smaller value to the left by removing elements that cannot be valid candidates.

const numbers = [4, 5, 2, 10, 8];

const result = new Array(numbers.length).fill(-1);
const stack = [];

for (let i = 0; i < numbers.length; i++) {
  while (
    stack.length > 0 &&
    stack[stack.length - 1] >= numbers[i]
  ) {
    stack.pop();
  }

  if (stack.length > 0) {
    result[i] = stack[stack.length - 1];
  }

  stack.push(numbers[i]);
}

console.log(result);
// [-1, 4, -1, 2, 2]

The Four Common Patterns

Problem	Typical Direction	Stack Behavior
Next greater	Right to left	Remove smaller or equal values
Next smaller	Right to left	Remove greater or equal values
Previous greater	Left to right	Remove smaller or equal values
Previous smaller	Left to right	Remove greater or equal values

Monotonic Stack with Indexes

In many problems, storing values alone is not enough. You may need to know the position where an element occurred. In that case, store indexes in the stack and use those indexes to access the original array.

const numbers = [2, 1, 2, 4, 3];
const result = new Array(numbers.length).fill(-1);
const stack = [];

for (let i = numbers.length - 1; i >= 0; i--) {
  while (
    stack.length > 0 &&
    numbers[stack[stack.length - 1]] <= numbers[i]
  ) {
    stack.pop();
  }

  if (stack.length > 0) {
    result[i] = numbers[stack[stack.length - 1]];
  }

  stack.push(i);
}

console.log(result);
// [4, 2, 4, -1, -1]

Index-based stacks are especially useful when the answer requires a distance, position, or range rather than only the neighboring value.

Daily Temperatures Pattern

A classic monotonic stack problem asks how many days a person must wait before encountering a warmer temperature.

For example:

Temperatures:
[73, 74, 75, 71, 69, 72, 76, 73]

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

The stack stores indexes of temperatures that are still waiting for a warmer day. When a warmer temperature is encountered, the waiting indexes can be resolved.

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];

const answer = new Array(temperatures.length).fill(0);
const stack = [];

for (let i = 0; i < temperatures.length; i++) {
  while (
    stack.length > 0 &&
    temperatures[i] > temperatures[stack[stack.length - 1]]
  ) {
    const previousIndex = stack.pop();
    answer[previousIndex] = i - previousIndex;
  }

  stack.push(i);
}

console.log(answer);
// [1, 1, 4, 2, 1, 1, 0, 0]

Largest Rectangle in a Histogram

Another important application is finding the largest rectangular area in a histogram. A monotonic increasing stack can identify the nearest smaller bars on either side of each bar, which determines how far that bar can extend.

This problem demonstrates that monotonic stacks are not limited to simply finding the next greater or smaller value. They can also maintain boundaries for more complex range calculations.

Why the Algorithm Is O(n)

The nested while loop can initially look like it makes the algorithm quadratic. However, every element is pushed onto the stack at most once and popped at most once.

Therefore, across the entire traversal, the total number of stack operations is proportional to n.

Complexity

Time: O(n)
Auxiliary space: O(n)

When Should You Think of a Monotonic Stack?

A monotonic stack is worth considering when a problem has a combination of the following characteristics:

The input is a sequence or array.
You need the closest element to the left or right.
The question asks for greater or smaller relationships.
A naive solution would repeatedly scan to the left or right.
Previously encountered elements become irrelevant after a new value appears.

Monotonic Stack vs Regular Stack

Regular Stack	Monotonic Stack
Primarily follows LIFO behavior	Follows LIFO behavior and maintains an order
No required relationship between values	Values follow increasing or decreasing order
Used for general stack problems	Often used for nearest greater/smaller problems

Common Mistakes

Choosing the wrong increasing or decreasing stack pattern.
Using the wrong comparison operator when removing elements.
Confusing next elements with previous elements.
Storing values when indexes are required to calculate distances.
Forgetting to process or interpret elements remaining in the stack.
Assuming a nested while loop automatically means O(n²) complexity.
Failing to test duplicate values, which can expose incorrect equality handling.

Key Takeaways

A monotonic stack maintains elements in increasing or decreasing order.
It is commonly used for next greater, next smaller, previous greater, and previous smaller problems.
Elements that cannot become useful candidates are removed from the stack.
Each element is generally pushed and popped at most once.
Many monotonic stack algorithms run in O(n) time.
Store indexes instead of values when the problem requires distances or positions.
Recognizing the nearest-greater or nearest-smaller pattern is the key to using this technique effectively.

Topics

Monotonic Stack Data Structure