Understanding Monotonic Stacks

January 24, 2025 | Data Structures

A Monotonic Stack is a specialized data structure that maintains elements in a specific order (either increasing or decreasing). It is commonly used in problems involving finding the next greater or next smaller element efficiently.

When to Use Monotonic Stacks

Monotonic stacks are useful in problems that require:

• Finding the next/previous greater/smaller element in an array.
• Efficient range queries where elements are processed in a linear order.
• Optimizing brute-force solutions that involve nested loops.

Common Use Cases

• Next Greater Element problems
• Stock Span problems
• Histogram Largest Rectangle problems
• Trapping Rain Water problems

How a Monotonic Stack Works

The stack maintains a monotonic property:

• Increasing Stack: The elements are in ascending order (smallest at the bottom, largest at the top).
• Decreasing Stack: The elements are in descending order (largest at the bottom, smallest at the top).

Implementation of a Monotonic Stack

Example: Next Greater Element

function nextGreaterElements(nums) {
  let stack = [], result = Array(nums.length).fill(-1);
  
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      let index = stack.pop();
      result[index] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

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

Explanation

1. Traverse the array.
2. While the stack is not empty and the current element is greater than the stack’s top element, pop elements from the stack.
3. The popped element’s index gets assigned the current element as its next greater element.
4. Push the current index to the stack.
5. If no greater element is found, it remains -1.

Time and Space Complexity

• Time Complexity: O(n) - Each element is pushed and popped at most once.
• Space Complexity: O(n) - In the worst case, all elements are stored in the stack.