Monotonic Stack: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Monotonic Stack: Complete Guide with Examples

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. The main template solves the next greater element problem, and the variations cover the flipped comparison, the left-to-right variant, and the circular array trick.

Main Template: Next Greater Element

Every element must find the first greater value to its right. The stack stores indices, not values, and holds only elements whose answer is still unknown. Each new value resolves the unanswered elements smaller than itself.

Use this for Next Greater Element I .

function nextGreaterElement(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = []; // indices still waiting for an answer

    for (let i = 0; i < n; i++) {
        // Any waiting element smaller than the current value
        // finally has its next greater element right here.
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    result = [-1] * len(nums)
    stack = []  # indices still waiting for an answer

    for i in range(len(nums)):
        # A larger value arrived, so everyone smaller on the
        # stack finally gets their next greater element.
        while stack and nums[i] > nums[stack[-1]]:
            result[stack.pop()] = nums[i]
        stack.append(i)

    return result

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting

        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;
    }
}

#include <vector>
#include <stack>

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st; // indices still waiting for an answer

    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{} // indices still waiting

    for i, num := range nums {
        // The current value resolves every waiting index
        // whose value is smaller, so pop them into the result.
        for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
            result[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return result
}

def next_greater_element(nums)
    result = Array.new(nums.length, -1)
    stack = [] # indices still waiting for an answer

    nums.each_with_index do |num, i|
        while !stack.empty? && num > nums[stack.last]
            result[stack.pop] = num
        end
        stack.push(i)
    end

    result
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

stack: stores indices of elements whose next greater value is still unknown. Indices, never values, because you need the position to write into result.
result: the answer array, prefilled with -1 for elements that never find a greater value.
nums[i]: the current element. It acts as the resolver for everything smaller that is already on the stack.

Visual Mechanism

    graph TD
    A["Current index i"] --> B{"Stack not empty and nums[i] > nums[top]?"}
    B -- "Yes" --> C["Pop top. result[top] = nums[i]"]
    C --> B
    B -- "No" --> D["Push i onto the stack"]
    D --> E["Move to i + 1"]

Critical Sections

The while condition is the whole pattern. It combines two checks: the stack contains something, and the current value beats the value above it. Only when both hold does the top element find its answer, so it gets popped and recorded. When the condition fails, either the stack is empty or the current value satisfies the sorted order, and the current index becomes the newest open candidate.

The push is what keeps the stack sorted. Everything that breaks the order has been popped above, so the current value always fits at the top. That ordering is also why the top is always the smallest open value, which is the only element the next arriving value can answer.

Initialization matters too. The -1 fill stays correct even when the whole array is sorted descending. An empty array returns an empty list without touching the loop, so there is no off-by-one to handle.

Variations

1. Next Smaller Element

Flip the comparison from > to < and the same skeleton answers the next smaller element instead. The stack now keeps an increasing order.

Use this for practice before Sum of Subarray Minimums , which is built on finding nearby smaller elements.

function nextSmallerElement(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = []; // indices still waiting

    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

from typing import List

def next_smaller_element(nums: List[int]) -> List[int]:
    result = [-1] * len(nums)
    stack = []  # indices still waiting

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

    return result

class Solution {
    public int[] nextSmallerElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        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;
    }
}

func nextSmallerElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{}

    for i, num := range nums {
        for len(stack) > 0 && num < nums[stack[len(stack)-1]] {
            result[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return result
}

def next_smaller_element(nums)
    result = Array.new(nums.length, -1)
    stack = []

    nums.each_with_index do |num, i|
        while !stack.empty? && num < nums[stack.last]
            result[stack.pop] = num
        end
        stack.push(i)
    end

    result
end

The only difference is the operator, so this variant is a good memorization anchor. When a problem says “nearest smaller value to the right,” reuse the skeleton and switch the comparison.

2. Previous Greater Element

The same idea answers to the left. Instead of popping into the result, you pop the candidates that cannot be an answer for the current index, and whatever remains on top is the answer.

Use this to understand the boundary computation in Sum of Subarray Minimums .

function previousGreaterElement(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];

    for (let i = 0; i < n; i++) {
        // Candidates not greater than the current value are
        // hopeless, they can never answer anyone behind them.
        while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
            stack.pop();
        }
        result[i] = stack.length > 0 ? nums[stack[stack.length - 1]] : -1;
        stack.push(i);
    }
    return result;
}

from typing import List

def previous_greater_element(nums: List[int]) -> List[int]:
    result = [-1] * len(nums)
    stack = []

    for i in range(len(nums)):
        # Any candidate that is not strictly greater than the
        # current value can never be an answer to the left.
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        result[i] = nums[stack[-1]] if stack else -1
        stack.append(i)

    return result

class Solution {
    public int[] previousGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
            stack.push(i);
        }
        return result;
    }
}

func previousGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{}

    // Keep only candidates strictly greater than nums[i], since
    // anything smaller or equal can never answer another element
    // that comes after it.
    for i, num := range nums {
        for len(stack) > 0 && nums[stack[len(stack)-1]] <= num {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            result[i] = nums[stack[len(stack)-1]]
        }
        stack = append(stack, i)
    }
    return result
}

def previous_greater_element(nums)
    result = Array.new(nums.length, -1)
    stack = []

    nums.each_with_index do |num, i|
        while !stack.empty? && nums[stack.last] <= num
            stack.pop
        end
        result[i] = stack.empty? ? -1 : nums[stack.last]
        stack.push(i)
    end

    result
end

The subtle part in this variant is the <= in the pop condition. Equal values are not strictly greater, so they cannot be the answer and must be removed from the stack along with smaller ones.

3. Circular Next Greater

Scan the array twice and the second pass simulates wrapping around. Anything still unanswered after the first lap can still resolve on the lap that follows the end.

Use this for Next Greater Element II .

function nextGreaterElements(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = [];

    // Two laps give every element a shot at anything behind it.
    for (let i = 0; i < 2 * n; i++) {
        const cur = nums[i % n];
        while (stack.length > 0 && nums[stack[stack.length - 1]] < cur) {
            result[stack.pop()] = cur;
        }
        if (i < n) {
            stack.push(i);
        }
    }
    return result;
}

from typing import List

def next_greater_elements(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack = []

    # Two passes simulate the circle; each index is pushed
    # only on the first pass so it resolves at most once.
    for i in range(2 * n):
        cur = nums[i % n]
        while stack and nums[stack[-1]] < cur:
            result[stack.pop()] = cur
        if i < n:
            stack.append(i)

    return result

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        // Two laps simulate the circle; indices enter the stack
        // only during the first lap to avoid duplicates.
        for (int i = 0; i < 2 * n; i++) {
            int cur = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < cur) {
                result[stack.pop()] = cur;
            }
            if (i < n) {
                stack.push(i);
            }
        }
        return result;
    }
}

#include <vector>
#include <stack>

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;

    for (int i = 0; i < 2 * n; i++) {
        int cur = nums[i % n];
        while (!st.empty() && nums[st.top()] < cur) {
            result[st.top()] = cur;
            st.pop();
        }
        if (i < n) {
            st.push(i);
        }
    }
    return result;
}

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{}

    for i := 0; i < 2*n; i++ {
        cur := nums[i%n]
        for len(stack) > 0 && nums[stack[len(stack)-1]] < cur {
            result[stack[len(stack)-1]] = cur
            stack = stack[:len(stack)-1]
        }
        if i < n {
            stack = append(stack, i)
        }
    }
    return result
}

The double pass must push each index only during the first lap, otherwise the same index sits on the stack twice. Values that never meet a larger one, like the maximum, keep their -1 through both laps.

The circular variant keeps the same

O(N)

time and space as the base pattern, since the second lap processes the same N indices at most once each.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .