Introduction

The Monotonic Stack Pattern is a specialized stack technique used to solve problems involving the next greater element, next smaller element, previous greater element, previous smaller element, and many interval-based optimization problems.

Unlike a normal stack, a Monotonic Stack always maintains its elements in either:

• Increasing order
• Decreasing order

This property allows many seemingly O(n²) problems to be solved efficiently in O(n) time.

It is one of the most common medium-level coding interview patterns.

---

When Should You Use Monotonic Stack?

Use this pattern when the problem asks for:

• Next Greater Element
• Next Smaller Element
• Previous Greater Element
• Previous Smaller Element
• Largest Rectangle in Histogram
• Daily Temperatures
• Stock Span Problem
• Trapping Rain Water (optimized approach)
• Sum of Subarray Minimums

Typical interview keywords:

• Next
• Previous
• Greater
• Smaller
• Nearest
• Span
• Histogram
• Stack

---

Core Idea

Maintain a stack that is always sorted.

For every new element,

remove elements that violate the monotonic order.

graph TD
    Current_Element["Current Element"] --> Compare_With_Stack_Top["Compare With Stack Top"]
    Compare_With_Stack_Top["Compare With Stack Top"] --> Pop_While_Invalid["Pop While Invalid"]
    Pop_While_Invalid["Pop While Invalid"] --> Push_Current_Element["Push Current Element"]
    Push_Current_Element["Push Current Element"] --> Continue["Continue"]

Each element is pushed and popped at most once.

---

Types of Monotonic Stacks

Increasing Stack

Elements remain in increasing order.

Bottom

2

4

7

Top

Useful for:

• Next Smaller Element
• Previous Smaller Element
• Histogram Problems

---

Decreasing Stack

Elements remain in decreasing order.

Bottom

9

7

5

Top

Useful for:

• Next Greater Element
• Previous Greater Element
• Stock Span

---

Visualization

Find Next Greater Element

Input

2 1 5 3 6

Process

graph TD
    Stack["Stack"] --> N_2["2"]
    N_2["2"] --> N_2_1["2 1"]
    N_2_1["2 1"] --> Pop_1["Pop 1"]
    Pop_1["Pop 1"] --> Pop_2["Pop 2"]
    Pop_2["Pop 2"] --> Push_5["Push 5"]
    Push_5["Push 5"] --> N_5_3["5 3"]
    N_5_3["5 3"] --> Pop_3["Pop 3"]
    Pop_3["Pop 3"] --> Pop_5["Pop 5"]
    Pop_5["Pop 5"] --> N_6["6"]

Result

2 → 5

1 → 5

5 → 6

3 → 6

6 → -1

---

Generic Algorithm

graph TD
    Create_Empty_Stack["Create Empty Stack"] --> Traverse_Array["Traverse Array"]
    Traverse_Array["Traverse Array"] --> Stack_Not_Empty["Stack Not Empty?"]
    Stack_Not_Empty["Stack Not Empty?"] --> Current_Better_Than_Top["Current Better Than Top?"]
    Current_Better_Than_Top["Current Better Than Top?"] --> Yes["Yes"]
    Yes["Yes"] --> Pop["Pop"]
    Pop["Pop"] --> Repeat["Repeat"]
    Repeat["Repeat"] --> Push_Current["Push Current"]
    Push_Current["Push Current"] --> Continue["Continue"]

---

Java Example

Next Greater Element

import java.util.*;

public class NextGreaterElement {

    public static int[] nextGreater(int[] nums) {

        int n = nums.length;

        int[] result = new int[n];

        Arrays.fill(result, -1);

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {

            while (!stack.isEmpty()
                    && nums[i] > nums[stack.peek()]) {

                result[stack.pop()] = nums[i];

            }

            stack.push(i);

        }

        return result;

    }

}

---

Internal Working

Input

2 1 5 3 6

Stack Stores

Indexes

Process

graph TD
    Push_2["Push 2"] --> Push_1["Push 1"]
    Push_1["Push 1"] --> Current_5["Current = 5"]
    Current_5["Current = 5"] --> Pop_1["Pop 1"]
    Pop_1["Pop 1"] --> Answer_5["Answer = 5"]
    Answer_5["Answer = 5"] --> Pop_2["Pop 2"]
    Pop_2["Pop 2"] --> Answer_5["Answer = 5"]
    Answer_5["Answer = 5"] --> Push_5["Push 5"]

Continue until the array ends.

---

Largest Rectangle in Histogram

Histogram

2 1 5 6 2 3

The stack stores increasing bar heights.

Whenever a smaller bar appears,

calculate the rectangle area.

Area

=

Height

×

Width

This converts a brute-force O(n²) solution into an O(n) solution.

---

Daily Temperatures

Input

73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0

Use a decreasing stack of indices to determine how many days must pass until a warmer temperature occurs.

---

Stock Span Problem

Input

100 80 60 70 60 75 85

Output

1 1 1 2 1 4 6

Use a decreasing stack to efficiently compute consecutive days with smaller or equal prices.

---

Complexity Analysis

Each element is:

• Pushed once
• Popped once

Therefore,

Operation	Complexity
Time	O(n)
Space	O(n)

Even though nested loops appear in the code, the total work remains linear.

---

Why O(n)?

Suppose the input is:

5 4 3 2 1

Each value is pushed exactly once.

Suppose the input is:

1 2 3 4 5

Each value is pushed once and popped once.

No element is processed more than twice.

Hence,

Total Operations

≤ 2 × n

which is O(n).

---

Monotonic Stack vs Normal Stack

Feature	Normal Stack	Monotonic Stack
Ordering	None	Always Sorted
Push	Always	Conditional
Pop	Manual	Automatic While Condition
Complexity	Depends	Usually O(n)
Best For	General Stack Problems	Next/Previous Greater/Smaller

---

Common Monotonic Stack Problems

Problem	Difficulty
Next Greater Element I	Easy
Next Greater Element II	Medium
Daily Temperatures	Medium
Stock Span	Medium
Largest Rectangle in Histogram	Hard
Maximal Rectangle	Hard
Trapping Rain Water	Hard
Sum of Subarray Minimums	Hard
Online Stock Span	Medium

---

Production Use Cases

Stock Market Analytics

Calculate stock span and price trends.

---

Weather Forecasting

Predict the next warmer or cooler day.

---

Monitoring Systems

Find the next higher CPU, memory, or latency spike.

---

Financial Trading

Analyze future price movements efficiently.

---

Histogram Analytics

Calculate maximum rectangular regions in dashboards.

---

Manufacturing

Detect the next larger sensor measurement.

---

Recommendation Systems

Identify the next higher-rated item in a sequence.

---

Time-Series Analysis

Analyze peaks, valleys, and neighboring events.

---

Common Mistakes

Using Values Instead of Indices

Many problems require distances or positions, so store indices rather than values.

---

Choosing the Wrong Stack Type

• Increasing Stack → Smaller element problems
• Decreasing Stack → Greater element problems

---

Forgetting Remaining Elements

After traversal, process or initialize unresolved elements (often -1 or 0).

---

Incorrect Pop Condition

Ensure the comparison matches the problem (>, <, >=, or <=).

---

Using Stack Instead of Deque

For modern Java code, ArrayDeque is generally preferred over the legacy Stack class because it provides better performance and cleaner semantics for stack operations.

Example:

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.pop();
stack.peek();

---

Interview Tips

Mention these observations:

• Every element is pushed once and popped once.
• The stack maintains a monotonic order throughout processing.
• Most problems store indices instead of values.
• Carefully decide between increasing and decreasing stacks.
• Even with nested loops, the overall complexity is O(n) due to amortized analysis.

---

Frequently Asked Interview Questions

1. What is a Monotonic Stack?

Answer

A Monotonic Stack is a stack that always maintains its elements in either increasing or decreasing order while processing data.

---

2. Why is it called "monotonic"?

Answer

Because the elements in the stack follow a monotonic (consistently increasing or consistently decreasing) order.

---

3. What is the time complexity?

Answer

O(n) because each element is pushed and popped at most once.

---

4. When should an increasing stack be used?

Answer

For problems involving the next or previous smaller element and histogram-related calculations.

---

5. When should a decreasing stack be used?

Answer

For problems involving the next or previous greater element, stock span, and similar comparisons.

---

6. Why do many implementations store indices?

Answer

Indices make it easy to calculate distances, widths, spans, and retrieve the original values when needed.

---

7. Which interview problems commonly use this pattern?

Answer

Next Greater Element, Daily Temperatures, Stock Span, Largest Rectangle in Histogram, Trapping Rain Water, and Sum of Subarray Minimums.

---

8. Where is the Monotonic Stack used in production?

Answer

Financial analytics, weather forecasting, monitoring systems, time-series analysis, manufacturing, and histogram-based optimization.

---

9. What is the biggest mistake candidates make?

Answer

Using the wrong monotonic order (increasing vs. decreasing) or storing values when indices are required.

---

10. Why is this pattern considered important?

Answer

It transforms many quadratic scanning problems into efficient linear-time solutions by maintaining a carefully ordered stack.

---

Quick Revision

Topic	Summary
Pattern	Monotonic Stack
Data Structure	Stack / Deque
Types	Increasing, Decreasing
Time Complexity	O(n)
Space Complexity	O(n)
Best For	Next/Previous Greater/Smaller, Span, Histogram
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• A Monotonic Stack maintains elements in a strictly increasing or decreasing order.
• Each element is pushed and popped at most once, resulting in O(n) time complexity.
• Choosing the correct monotonic order is crucial for solving problems correctly.
• Storing indices instead of values simplifies span, width, and distance calculations.
• Mastering this pattern prepares you for advanced interview problems involving nearest-element queries, histograms, stock analysis, and time-series processing.

---