In competitive programming and technical interviews, the Monotonic Stack is one of the most powerful patterns used to solve array-based problems with time constraints. Let’s break it down and see how it can be a game-changer in your algorithm arsenal.

🔍 What is a Monotonic Stack?

A Monotonic Stack is a stack that is maintained in either increasing or decreasing order. It is not a data structure on its own, but a technique used to solve problems related to:

  • Next Greater / Smaller Element
  • Previous Greater / Smaller Element
  • Stock Span
  • Trapping Rain Water
  • Largest Rectangle in Histogram
  • Daily Temperatures

🧭 Types of Monotonic Stacks

Stack Type Maintains Used For
Increasing Increasing order (bottom → top) Next Smaller Element
Decreasing Decreasing order (bottom → top) Next Greater Element

🧠 Core Idea

  • Push values while maintaining order.
  • Pop from the stack if the current element breaks the order.
  • Helps find nearest elements (to the left or right) efficiently.

📘 Example 1: Next Greater Element

🔧 Problem:

Given an array, for each element, find the next greater element to its right.

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();

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

⏱ Time Complexity: O(n)

📘 Example 2: Previous Smaller Element

🔧 Problem:

Find the nearest smaller element to the left for every element.

public int[] previousSmallerElement(int[] nums) {
    int[] result = new int[nums.length];
    Stack<Integer> stack = new Stack<>();

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

📘 Example 3: Largest Rectangle in Histogram

🔧 Problem:

Given the heights of bars in a histogram, find the largest rectangular area.

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

📌 Concept: This uses both next and previous smaller concepts in a single pass.

📘 Example 4: Trapping Rain Water

🔧 Problem:

Given an elevation map, compute how much water can be trapped.

public int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int water = 0, i = 0;

    while (i < height.length) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int top = stack.pop();
            if (stack.isEmpty()) break;

            int distance = i - stack.peek() - 1;
            int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
            water += distance * boundedHeight;
        }
        stack.push(i++);
    }
    return water;
}

📘 Example 5: Daily Temperatures

🔧 Problem:

Return an array where res[i] = days until a warmer temperature.

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            result[prev] = i - prev;
        }
        stack.push(i);
    }
    return result;
}

💡 Key Takeaways

  • Use increasing or decreasing stacks based on the problem.
  • Monotonic stacks help you reduce time complexity from O(n²) to O(n).
  • Commonly used in sliding window, range-based, and histogram problems.

🎯 Final Tip

Always ask:

  • Do I need the next/previous greater/smaller element?
  • Do I need it to the left or to the right?

If yes → 💡 Monotonic Stack is your friend!