Monotonic Stack

A monotonic stack is a stack that exhibits the property of elements arranged in a particular sorting order like:

• Strictly increasing (>)

• Non-decreasing (>=)

• Strictly decreasing (<)

• Non-increasing (<=)

Arrays and their sorted orders

The general template of the algorithm looks like this:

public class Solution {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5};
        Stack<Integer> stack = new Stack<>();
        
        // Iterating using indexes as we might store indexes rather than values
        for(int i=0;i<nums.length;i++) {
            // Here operator can be filled according to the given condition
            // Strictly increasing (>)
            // Non-decreasing (>=)
            // Strictly decreasing (<)
            // Non-increasing (<=)
            while(!stack.isEmpty() && stack.peek() `OPERATOR` nums[i]) {
                int stackTop = stack.pop();
                
                 // do something with stackTop here e.g.
                // nextGreater[stackTop] = i
            }
            if(!stack.isEmpty()) {
                // if stack has some elements left
               // do something with stack top here e.g.
              // previousGreater[i] = stack.peek()
            }
            stack.push(i);
        }
        
    }
}
    

Notes about the template above

• We initialize an empty stack at the beginning.

• The stack contains the index of items in the array, not the items themselves

• There is an outer for loop and inner while loop.

• At the beginning of the program, the stack is empty, so we don't enter the while loop at first.

• The earliest we can enter the while loop body is during the second iteration of for loop. That's when there is at least an item in the stack.

• At the end of the while loop, the index of the current element is pushed into the stack

• The OPERATOR inside the while loop condition decides what type of monotonic stack are we creating.

• The OPERATOR could be any of the four - >, >=, <, <=

Monotonic Stack Types

Problem	Stack Type	Operator in while loop	Assignment Position
next greater	decreasing (equal allowed)	stackTop < current	inside while loop
previous greater	decreasing (strict)	stackTop <= current	outside while loop
next smaller	increasing (equal allowed)	stackTop > current	inside while loop
previous smaller	increasing (strict)	stackTop >= current	outside while loop

StrictlyIncreasingStack

class Solution {
    public int[] getMonotonicStrictlyIncreasingStack(int[] input) {
        int n = input.length;
        int[] stack = new int[n];
        int top = -1; // Stack top pointer

        for (int i = 0; i < n; i++) {
            // When you encounter a number from input which is greater than stack top
            // Keep popping elements from stack that are greater than current element
            while (top >= 0 && stack[top] > input[i]) {
                top--; // Pop elements greater than current element from stack
            }
            stack[++top] = input[i]; // Push current element onto stack
        }

        // Create a new array with elements from the stack
        int[] result = new int[top + 1];
        System.arraycopy(stack, 0, result, 0, top + 1);

        return result;
    }
}

NonDecreasingStack

class Solution {
    public int[] getMonotonicNonDecreasingStack(int[] input) {
        int n = input.length;
        int[] stack = new int[n];
        int top = -1; // Stack top pointer

        for (int i = 0; i < n; i++) {
            // When you encounter a number from input which is greater than or equal
            // stack top
            // Keep popping elements from stack that are greater than or equal
            // than current element
            while (top >= 0 && stack[top] >= input[i]) {
                top--; // Pop elements greater than current element from stack
            }
            stack[++top] = input[i]; // Push current element onto stack
        }

        // Create a new array with elements from the stack
        int[] result = new int[top + 1];
        System.arraycopy(stack, 0, result, 0, top + 1);

        return result;
    }
}

StrictlyDecreasingStack

class Solution {
    public int[] getMonotonicStrictlyDecreasingStack(int[] input) {
        int n = input.length;
        int[] stack = new int[n];
        int top = -1; // Stack top pointer

        for (int i = 0; i < n; i++) {
            // When you encounter a number from input which is lesser than stack top
            // Keep popping elements from stack that are lesser than current element
            while (top >= 0 && stack[top] < input[i]) {
                top--; // Pop elements greater than current element from stack
            }
            stack[++top] = input[i]; // Push current element onto stack
        }

        // Create a new array with elements from the stack
        int[] result = new int[top + 1];
        System.arraycopy(stack, 0, result, 0, top + 1);

        return result;
    }
}

NonIncreasingStack

class Solution {
    public int[] getMonotonicNonIncreasingStack(int[] input) {
        int n = input.length;
        int[] stack = new int[n];
        int top = -1; // Stack top pointer

        for (int i = 0; i < n; i++) {
            // When you encounter a number from input which is lesser than or equal
            // stack top
            // Keep popping elements from stack that are less or equal than current element
            while (top >= 0 && stack[top] < input[i]) {
                top--; // Pop elements greater than current element from stack
            }
            stack[++top] = input[i]; // Push current element onto stack
        }

        // Create a new array with elements from the stack
        int[] result = new int[top + 1];
        System.arraycopy(stack, 0, result, 0, top + 1);

        return result;
    }
}

Time Complexity

Operation	Best	Worst	Average	Explanation
Push	O(1)	O(1)	O(1)	Pushing an element onto the stack takes constant time.
Pop	O(1)	O(1)	O(1)	Popping an element from the stack takes constant time.
Top	O(1)	O(1)	O(1)	Retrieving the top element of the stack takes constant time.
Finding Next Greater/Smaller Element	O(1)	O(n)	O(n)	Finding the next greater/smaller element for each element in the stack can have a best case of constant time when the elements are in non-decreasing/non-increasing order. However, in the worst case, it may require traversing the entire stack, resulting in a linear time complexity.
Calculating Nearest Smaller/Larger Elements	O(1)	O(n)	O(n)	Calculating the nearest smaller/larger elements for each element in the stack can have a best case of constant time when the elements are in non-decreasing/non-increasing order. However, in the worst case, it may require traversing the entire stack, resulting in a linear time complexity.

Space Complexity

Operation	Best	Worst	Average	Explanation
Push	O(1)	O(1)	O(1)	Pushing an element onto the stack takes constant space.
Pop	O(1)	O(1)	O(1)	Popping an element from the stack takes constant space.
Top	O(1)	O(1)	O(1)	Retrieving the top element of the stack takes constant space.
Finding Next Greater/Smaller Element	O(n)	O(n)	O(n)	Finding the next greater/smaller element for each element in the stack requires storing the result for each element, resulting in a space complexity linear to the size of the stack (O(n)).
Calculating Nearest Smaller/Larger Elements	O(n)	O(n)	O(n)	Calculating the nearest smaller/larger elements for each element in the stack requires storing the result for each element, resulting in a space complexity linear to the size of the stack (O(n)).

Problems

• Basic: 496-Next Greater Element I and 1019-Next Greater Node In Linked List.

• Dealing with circular list: 503-Next Greater Element II.

• Variant: 042-Trapping Rain Water.

• Variant: 084-Largest Rectangle in Histogram.

References:

• A comprehensive guide and template for monotonic stack based problems - LeetCode Discuss

• Algorithms for Interview 2: Monotonic Stack | by Yang Zhou | TechToFreedom | Medium