Code Templates

Note

This page provides standardized code blueprints for the Monotonic Stack pattern. These templates are designed to be easily adapted for various coding interview problems.

The “Main” Template: Next Greater Element

The most common application of a monotonic stack is finding the Next Greater Element (NGE). We use a monotonic decreasing stack to store indices of elements that haven’t found their “greater” match yet.

Implementation

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function nextGreaterElement(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack = []; // Stores indices

    for (let i = 0; i < n; i++) {
        // While stack is not empty and current > top of stack
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const index = stack.pop();
            result[index] = nums[i];
        }
        stack.push(i);
    }

    return result;
}

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack = [] # Stores indices

    for i in range(n):
        # We want a decreasing stack.
        # If current number > top of stack, we found its match.
        while stack and nums[i] > nums[stack[-1]]:
            index = stack.pop()
            result[index] = 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<>(); // Stores indices

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

#include <vector>
#include <stack>

using namespace std;

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> s; // Stores indices

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

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

    var stack []int // Stores indices

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

    return result
}

def next_greater_element(nums)
  n = nums.length
  result = Array.new(n, -1)
  stack = [] # Stores indices

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

  result
end

Code Breakdown

Key Variables

stack: Stores the indices of elements. We store indices rather than values because we often need to calculate the distance between elements or update a specific position in the result array.
result: Initialized with -1 (or 0 for distance problems like Daily Temperatures).
nums[i]: The “incoming” element that attempts to pop elements from the stack.

Visualizing the Mechanics

This Mermaid diagram shows how the stack maintains its monotonic property during a single iteration:

  graph TD
    A["Current element: nums[i]"] --> B{"Stack empty or nums[i] <= nums[top]?"}
    B -- No --> C["Pop top"]
    C --> D["Set result[top] = nums[i]"]
    D --> B
    B -- Yes --> E["Push i to stack"]
    E --> F["Move to i + 1"]

Variations

1. Next Smaller Element

To find the first smaller element to the right, simply change the comparison to nums[i] < nums[stack.top]. The stack will then be monotonically increasing.

2. Previous Greater/Smaller Element

To find the “previous” element (to the left), the logic is slightly different. Instead of popping when we find a match, we pop elements that cannot be the answer for the current element, and then the element currently at the top of the stack is our answer.

Example for Previous Greater Element:

for (let i = 0; i < n; i++) {
    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);
}

Practice

Apply these templates to the practice problems:

Practice Problems