Sandeep Bhardwaj

Backend Engineer • SaaS Builder

Monotonic stack helps find next/previous greater or smaller elements in linear time. It avoids repeated backward or forward scans.

Core Idea

Store indices in a stack with monotonic order of values.

  • decreasing stack -> next greater queries
  • increasing stack -> next smaller queries

Each index is pushed and popped at most once.

Template: Next Greater Element (Right)

public int[] nextGreaterRight(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> st = new ArrayDeque<>(); // stores indices

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

Problem 1: Daily Temperatures

public int[] dailyTemperatures(int[] t) {
    int n = t.length;
    int[] ans = new int[n];
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && t[i] > t[st.peek()]) {
            int j = st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

Problem 2: Next Greater Element II (Circular)

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (!st.isEmpty() && nums[idx] > nums[st.peek()]) {
            ans[st.pop()] = nums[idx];
        }
        if (i < n) st.push(idx);
    }
    return ans;
}

Problem 3: Largest Rectangle in Histogram

public int largestRectangleArea(int[] h) {
    int n = h.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();

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

Common Mistakes

  1. Storing values instead of indices when distance is required
  2. Choosing wrong monotonic direction
  3. Forgetting final flush pass
  4. Handling duplicates inconsistently (< vs <=)

Duplicate Tie-Breaking Rule

For contribution-count problems (like subarray minimums), duplicate handling must be asymmetric:

  • one side uses strict comparison (<)
  • other side uses non-strict (<=)

Without this, equal values may be double-counted or under-counted.

Document your tie rule before coding.

Debug Template

During development, log stack indices and values:

i=5 val=7 stack=[4(6),2(3)] -> pop 4, answer[4]=7

If results are wrong, inspect:

  • whether pops occur at correct comparator condition
  • whether unresolved indices are handled in final flush

Most monotonic stack bugs are comparator or flush mistakes.

  1. Next Greater Element I (LC 496)
    LeetCode
  2. Daily Temperatures (LC 739)
    LeetCode
  3. Next Greater Element II (LC 503)
    LeetCode
  4. Largest Rectangle in Histogram (LC 84)
    LeetCode
  5. Maximal Rectangle (LC 85)
    LeetCode
  6. Sum of Subarray Minimums (LC 907)
    LeetCode

Key Takeaways

  • Monotonic stacks solve neighbor/range-boundary queries in O(n).
  • Index storage is usually required for width/distance calculations.
  • The push-pop invariant is the core correctness argument.

Comments

You may also enjoy