LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Monotonic Stack & Queue/Monotonic Decreasing Stack: Template, Next Greater Element, and When to Use It

Monotonic Decreasing Stack: Template, Next Greater Element, and When to Use It

LeetCopilot Team
Dec 22, 2025
18 min read
Monotonic StackDecreasing StackNext Greater ElementStack TemplateInterview Prep
Master the monotonic decreasing stack pattern with production-ready templates in Python, JavaScript, and Java. Learn when to use decreasing order, solve next greater element problems, and avoid common mistakes.
Complete Guide

The Complete Monotonic Stack & Queue Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to monotonic stacks and queues. Learn all variants, when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any monotonic stack/queue problem.

Read the complete guide

The monotonic decreasing stack is one of the most elegant patterns in algorithm design. It solves "next greater element" problems in O(n) time—problems that would otherwise require O(n²) nested loops.

But here's what trips up most developers: understanding why decreasing order finds the next greater element. It seems counterintuitive. Why does maintaining smaller elements at the top help us find larger elements?

This comprehensive guide will teach you the complete decreasing stack template, the intuition behind why it works, when to apply it, and how to avoid the mistakes that cause wrong answers.

TL;DR

Use monotonic decreasing stack when:

  • Finding next greater element (to the right or left)
  • Finding previous greater element
  • Stack maintains decreasing order from bottom to top

Template:

python
stack = []  # Store indices
for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
        idx = stack.pop()
        # nums[i] is the next greater for nums[idx]
    stack.append(i)

Time: O(n), Space: O(n)

What Is a Monotonic Decreasing Stack?

Definition

A monotonic decreasing stack maintains elements in decreasing order from bottom to top.

Visual:

code
Bottom → Top
[9, 5, 3, 1]  ✓ Decreasing
[1, 3, 5, 9]  ✗ Increasing
[5, 5, 3, 1]  ✓ Non-strictly decreasing

The Invariant

Before pushing a new element, we pop all elements from the top that are smaller than or equal to the new element.

This maintains the decreasing property.

Example: Building a Decreasing Stack

code
Array: [3, 1, 4, 1, 5, 9, 2]

Step 1: Process 3
  Stack: [3]
  
Step 2: Process 1
  1 < 3, so just push
  Stack: [3, 1]  (decreasing ✓)
  
Step 3: Process 4
  4 > 1, pop 1
  4 > 3, pop 3
  Stack: [4]
  
Step 4: Process 1
  1 < 4, just push
  Stack: [4, 1]  (decreasing ✓)
  
Step 5: Process 5
  5 > 1, pop 1
  5 > 4, pop 4
  Stack: [5]
  
Step 6: Process 9
  9 > 5, pop 5
  Stack: [9]
  
Step 7: Process 2
  2 < 9, just push
  Stack: [9, 2]  (decreasing ✓)

Why Decreasing Order Finds Next Greater Element

The Key Insight

When you encounter an element larger than the stack top, you've found the next greater element for all smaller elements in the stack.

Visual proof:

code
Array: [2, 1, 5, 6, 2, 3]
       [0  1  2  3  4  5]  ← indices

i=0, val=2: stack=[0]
i=1, val=1: stack=[0,1]  (2 > 1, decreasing)
i=2, val=5: 
  - 5 > nums[1]=1, so 5 is next greater for index 1
  - 5 > nums[0]=2, so 5 is next greater for index 0
  - stack=[2]

Result so far:
  result[0] = 5  (next greater for 2)
  result[1] = 5  (next greater for 1)

Why This Works

The monotonic property guarantees:

  1. Elements in the stack are waiting for their next greater element
  2. They're in decreasing order, so when we find a larger element, it's the next greater for all smaller elements
  3. We pop them in order (smallest to largest), ensuring each gets the correct next greater

Mathematical Proof

For any element arr[i] in the stack:

  • All elements to its right in the stack are smaller (decreasing property)
  • All elements between arr[i] and current position were smaller (otherwise they'd still be in stack)
  • Therefore, the current element is the first element to the right that's greater than arr[i]

This is the definition of "next greater element."

The Universal Template

Python Template

python
def next_greater_element(nums):
    """
    Find next greater element for each position.
    
    Args:
        nums: List of integers
    
    Returns:
        List where result[i] = next greater element for nums[i],
        or -1 if no greater element exists
    
    Time: O(n) - each element pushed and popped at most once
    Space: O(n) - stack storage
    """
    n = len(nums)
    result = [-1] * n  # Default: no greater element
    stack = []  # Store indices (not values)
    
    for i in range(n):
        # Pop all elements smaller than current
        # These elements have found their next greater (nums[i])
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        
        # Push current index
        stack.append(i)
    
    # Elements remaining in stack have no next greater
    # (already initialized to -1)
    
    return result

# Example usage
print(next_greater_element([2, 1, 2, 4, 3]))
# Output: [4, 2, 4, -1, -1]
# Explanation:
# - Next greater for 2 (index 0) is 4
# - Next greater for 1 (index 1) is 2
# - Next greater for 2 (index 2) is 4
# - No next greater for 4 and 3

JavaScript Template

javascript
function nextGreaterElement(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        // Pop elements smaller than current
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = nums[i];
        }
        
        stack.push(i);
    }
    
    return result;
}

// Example
console.log(nextGreaterElement([2, 1, 2, 4, 3]));
// Output: [4, 2, 4, -1, -1]

Java Template

java
public int[] nextGreaterElement(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++) {
        // Pop elements smaller than current
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        
        stack.push(i);
    }
    
    return result;
}

Pattern 1: Next Greater Element I (LeetCode #496)

Problem

Given two arrays nums1 and nums2, where nums1 is a subset of nums2, find the next greater element for each element of nums1 in nums2.

Solution

python
def nextGreaterElement(nums1, nums2):
    """
    LeetCode #496: Next Greater Element I
    
    Time: O(n + m) where n = len(nums2), m = len(nums1)
    Space: O(n)
    """
    # Build next greater map for all elements in nums2
    next_greater = {}
    stack = []
    
    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    # Map nums1 elements to their next greater
    return [next_greater.get(num, -1) for num in nums1]

# Example
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(nextGreaterElement(nums1, nums2))
# Output: [-1, 3, -1]
# Explanation:
# - 4: no greater element in nums2
# - 1: next greater is 3
# - 2: no greater element after 2 in nums2

Why It Works

  1. Build a hash map of next greater elements for all of nums2
  2. Use monotonic decreasing stack to find next greater in O(n)
  3. Look up each element of nums1 in the map in O(1)

Pattern 2: Daily Temperatures (LeetCode #739)

Problem

Given daily temperatures, return an array where answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature.

Solution

python
def dailyTemperatures(temperatures):
    """
    LeetCode #739: Daily Temperatures
    
    Time: O(n)
    Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n  # Default: 0 days (no warmer day)
    stack = []  # Store indices
    
    for i in range(n):
        # While current temp is warmer than stack top
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx  # Days difference
        
        stack.append(i)
    
    return result

# Example
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]
# Explanation:
# - Day 0 (73°): next warmer is day 1 (74°), wait 1 day
# - Day 1 (74°): next warmer is day 2 (75°), wait 1 day
# - Day 2 (75°): next warmer is day 6 (76°), wait 4 days
# - Day 6 (76°): no warmer day, wait 0 days

Step-by-Step Trace

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

i=0, temp=73: stack=[0]
i=1, temp=74: 74 > 73, pop 0, result[0]=1-0=1, stack=[1]
i=2, temp=75: 75 > 74, pop 1, result[1]=2-1=1, stack=[2]
i=3, temp=71: 71 < 75, stack=[2,3]
i=4, temp=69: 69 < 71, stack=[2,3,4]
i=5, temp=72: 
  - 72 > 69, pop 4, result[4]=5-4=1
  - 72 > 71, pop 3, result[3]=5-3=2
  - 72 < 75, stack=[2,5]
i=6, temp=76:
  - 76 > 72, pop 5, result[5]=6-5=1
  - 76 > 75, pop 2, result[2]=6-2=4
  - stack=[6]
i=7, temp=73: 73 < 76, stack=[6,7]

Final result: [1, 1, 4, 2, 1, 1, 0, 0]

Pattern 3: Next Greater Element II (Circular Array)

Problem

Given a circular array, find the next greater element for every element. The next greater element of a number x is the first greater number to its traversing-order next in the array.

Solution

python
def nextGreaterElements(nums):
    """
    LeetCode #503: Next Greater Element II
    
    Handle circular array by iterating twice.
    
    Time: O(n)
    Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Iterate twice to handle circular nature
    for i in range(2 * n):
        idx = i % n  # Wrap around using modulo
        
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack.pop()] = nums[idx]
        
        # Only push indices in first iteration
        if i < n:
            stack.append(idx)
    
    return result

# Example
print(nextGreaterElements([1, 2, 1]))
# Output: [2, -1, 2]
# Explanation:
# - 1 (index 0): next greater is 2
# - 2 (index 1): no greater element (even circularly)
# - 1 (index 2): next greater is 2 (wrapping around)

Why Double Iteration?

Circular array means: After the last element, we continue from the first element.

Solution: Iterate through the array twice (2 * n iterations), using modulo to wrap indices.

Optimization: Only push indices during the first n iterations to avoid duplicates.

See detailed guide: Circular Arrays

Pattern 4: Previous Greater Element

Finding Previous Greater (Not Next)

To find the previous greater element (to the left), iterate right to left:

python
def previous_greater_element(nums):
    """
    Find previous greater element for each position.
    
    Time: O(n)
    Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Iterate right to left
    for i in range(n - 1, -1, -1):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        
        stack.append(i)
    
    return result

# Example
print(previous_greater_element([2, 1, 2, 4, 3]))
# Output: [-1, 2, -1, -1, 4]
# Explanation:
# - 2 (index 0): no previous greater
# - 1 (index 1): previous greater is 2
# - 2 (index 2): no previous greater
# - 4 (index 3): no previous greater
# - 3 (index 4): previous greater is 4

Alternative: Immediate Previous Greater

To find the immediate previous greater (not using stack popping):

python
def immediate_previous_greater(nums):
    """
    Find immediate previous greater element.
    Stack top is always the previous greater.
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(n):
        # Pop smaller elements
        while stack and nums[i] >= nums[stack[-1]]:
            stack.pop()
        
        # Stack top is previous greater
        if stack:
            result[i] = nums[stack[-1]]
        
        stack.append(i)
    
    return result

When to Use Decreasing Stack

✅ Use Decreasing Stack When:

  1. Finding next greater element

    • Keywords: "next greater," "next larger," "warmer temperature"
    • Direction: Left to right iteration

  2. Finding previous greater element

    • Keywords: "previous greater," "greater to the left"
    • Direction: Right to left iteration

  3. Stock span problems

    • Count consecutive days with price ≤ current
    • Uses decreasing stack

  4. Range queries with maximum

    • Finding ranges where element is maximum

❌ Don't Use Decreasing Stack When:

  1. Finding next smaller element

  2. Sliding window maximum

  3. Need all elements, not just extremes

    • Monotonic stack only tracks potential candidates

Common Mistakes

Mistake 1: Wrong Comparison Direction

❌ Wrong:

python
# Want next GREATER, but using < instead of >
while stack and nums[i] < nums[stack[-1]]:  # WRONG
    stack.pop()

✅ Correct:

python
# Next GREATER needs > comparison
while stack and nums[i] > nums[stack[-1]]:  # CORRECT
    idx = stack.pop()
    result[idx] = nums[i]

Mistake 2: Storing Values Instead of Indices

❌ Wrong:

python
stack.append(nums[i])  # Storing value
# Later: Can't calculate distance or access index

✅ Correct:

python
stack.append(i)  # Storing index
# Later: Can calculate i - stack[-1] for distance

When to store indices:

  • Need to calculate distances (Daily Temperatures)
  • Need to track positions
  • Need to access original array

See guide: Indices vs Values

Mistake 3: Not Initializing Result Array

❌ Wrong:

python
result = []  # Empty list
# Later: result[idx] = ... causes IndexError

✅ Correct:

python
result = [-1] * n  # Pre-initialized with default
# Elements without next greater already have -1

Mistake 4: Circular Array Without Double Iteration

❌ Wrong:

python
# Single iteration on circular array
for i in range(n):  # Misses wraparound cases
    # ...

✅ Correct:

python
# Double iteration with modulo
for i in range(2 * n):
    idx = i % n
    # ...

See guide: Next Greater Element Mistakes

Edge Cases

Edge Case 1: Empty Array

python
if not nums:
    return []

Edge Case 2: Single Element

python
nums = [5]
# Result: [-1] (no next greater)

Edge Case 3: Strictly Decreasing Array

python
nums = [5, 4, 3, 2, 1]
# Result: [-1, -1, -1, -1, -1]
# No element has a next greater

Edge Case 4: Strictly Increasing Array

python
nums = [1, 2, 3, 4, 5]
# Stack is always empty after popping
# Each element's next greater is the next element
# Result: [2, 3, 4, 5, -1]

Edge Case 5: Duplicates

python
nums = [2, 2, 2, 2]
# Use > (not >=) to keep duplicates in stack
# Result: [-1, -1, -1, -1]

See guide: Handling Duplicates

Complexity Analysis

Time Complexity: O(n)

Amortized analysis:

  • Each element is pushed exactly once: n operations
  • Each element is popped at most once: n operations
  • Total: 2n = O(n)

Even though there's a while loop inside the for loop, the total number of pops across all iterations is bounded by n.

Space Complexity: O(n)

Worst case: All elements in decreasing order

  • Stack contains all n elements
  • Space: O(n)

Best case: All elements in increasing order

  • Stack is always empty after popping
  • Space: O(n) for result array

See detailed proof: Why Stack Beats Brute Force

Practice Problems

Master the decreasing stack with these problems:

Beginner:

  1. Next Greater Element I (#496) - Basic template
  2. Next Greater Element II (#503) - Circular array
  3. Daily Temperatures (#739) - Classic application

Intermediate:
4. Online Stock Span (#901) - Streaming data
5. Final Prices With Special Discount (#1475) - Next smaller variant
6. Remove Nodes From Linked List (#2487) - Linked list variant

Advanced:
7. Sum of Subarray Ranges (#2104) - Bidirectional stack
8. 132 Pattern (#456) - Complex monotonic stack
9. Maximum Binary Tree (#654) - Tree construction

FAQ

Q: Why decreasing order for next greater?

A: When we find a larger element, we know it's the next greater for all smaller elements in the stack. Decreasing order ensures we process them correctly.

Q: Can I use >= instead of > in the while condition?

A: Depends on the problem. For basic next greater, use >. For contribution technique with duplicates, use >= on one side to avoid double-counting.

Q: Why store indices instead of values?

A: Indices let you calculate distances (Daily Temperatures) and access the original array. More flexible than storing values.

Q: How do I handle circular arrays?

A: Iterate twice (2 * n iterations) using modulo to wrap indices. Only push indices in the first n iterations.

Conclusion

The monotonic decreasing stack is a powerful pattern for finding next greater elements in O(n) time.

Key principles:

  • Decreasing order from bottom to top
  • Pop when current > stack top to find next greater
  • Store indices for flexibility
  • Each element pushed/popped once → O(n)

The template:

python
stack = []
for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
        result[stack.pop()] = nums[i]
    stack.append(i)

When to use:

  • "Next greater element"
  • "Daily temperatures"
  • "Stock span"

Master this template, and you'll solve dozens of LeetCode problems with confidence. For the opposite pattern, see Monotonic Increasing Stack Template. For the complete overview, see Monotonic Stack & Queue Guide.

Next time you see "next greater," reach for the decreasing stack.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials