📚 What is a Monotonic Stack

A monotonic stack is a standard stack data structure modified to keep its elements in a strict sorted order—either entirely increasing or entirely decreasing. It is used to solve range queries in linear time by discarding elements that can no longer affect future results.

⚙️ The Core Concept

As you iterate through an array, you push and pop elements from a data structure to maintain the sorted order.

For a Monotonic Increasing Stack:

When a new element comes in, compare it to the top of the stack.
If the new element is smaller than the top element, pop elements from the stack until the top is smaller than or equal to the new element.
Push the current element onto the stack.

For a Monotonic Decreasing Stack:

When a new element comes in, compare it to the top of the stack.
If the new element is greater than the top element, pop elements from the stack until the top is greater than or equal to the new element.
Push the current element onto the stack.

Why It Is Useful

Lightning Fast: By popping elements off instead of rescanning the array, every element is pushed and popped from the stack at most once. This results in an $O(N)$ time complexity.
Finds "Next Greater" Instantly: It tracks the exact distance or index to the next biggest (or smallest) number, which is incredibly useful for optimization puzzles.

Monotonic stack in action - Next greater element

The next greater element of some element $x$ in an array is the first greater element that is to the right of $x$ in the same array.

Example :

Input: nums = [4, 5, 2, 25, 7, 8]

Output: [5, 25, 25, -1, 8, -1]

Explanation: The next greater element for each value of nums is as follows:

for val 4 , next greater element is 5.
for val 5, next greater element is 25.
for val 2, next greater element is 25.
for val 25, There is no next greater element, so the answer is -1.
for val 7, next greater element is 8.
for val 8, There is no next greater element, so the answer is -1.

</> Python implementation

def next_greater_element(nums: list[int]) -> list[int]:

    # Initialize the results array filled with -1
    result = [-1] * len(nums)
    stack = []  # This will store indices of the elements

    for i in range(len(nums)):
        # While stack is not empty and current element is greater than the element 
        # corresponding to the index at the top of the stack
        while stack and nums[i] > nums[stack[-1]]:
            popped_index = stack.pop()
            result[popped_index] = nums[i]
            
        # Push the current index onto the stack
        stack.append(i)
        
    return result

# Example usage:
nums = [4, 5, 2, 25, 7, 8]
print(f"Input:  {nums}")
print(f"Output: {next_greater_element(nums)}")
# Output: [5, 25, 25, -1, 8, -1]

📌 Suggested problems

Next warmer day

Monotonic Stack