📉 Monotonic Stack

One-line summary: A stack that maintains a strictly increasing or decreasing order — enabling O(n) solutions for "next greater/smaller element" and span problems.

---

Concept

A monotonic stack is a stack where elements are always in monotonically increasing or decreasing order. When a new element violates the order, pop elements until the invariant is restored — those popped elements have found their answer.

Key insight: each element is pushed and popped at most once → O(n) total.

• Decreasing stack → used for "next greater element"
• Increasing stack → used for "next smaller element"

---

Diagram

---

Time & Space Complexity

Operation	Time	Space
Build NGE array	O(n)	O(n)
Daily Temperatures	O(n)	O(n)
Largest Rectangle in Histogram	O(n)	O(n)

---

Common Patterns

Pattern 1 — Next Greater Element

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // stores indices
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) result[stack.pop()] = nums[i];
    stack.push(i);
  }
  return result;
}

Pattern 2 — Daily Temperatures

function dailyTemperatures(temps) {
  const result = new Array(temps.length).fill(0);
  const stack = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }
  return result;
}

---

When to Use

• Finding next/previous greater or smaller elements
• Range-based problems with comparisons
• Span and width problems (largest rectangle, trapping rain)
• Stock span problems

---

Pitfalls

• Storing values instead of indices (indices let you compute distances)
• Forgetting to process remaining elements left in the stack at the end
• Confusing increasing vs decreasing stack direction

---

Practice Problems

Problem	Difficulty	Solution
LC 496 — Next Greater Element I	Easy	View Solution
LC 739 — Daily Temperatures	Medium	View Solution
LC 503 — Next Greater Element II	Medium
LC 901 — Online Stock Span	Medium
LC 84 — Largest Rectangle in Histogram	Hard
LC 42 — Trapping Rain Water	Hard
LC 85 — Maximal Rectangle	Hard
LC 907 — Sum of Subarray Minimums	Medium
LC 456 — 132 Pattern	Medium
CC — Monotonicity Check (MONOTON)	Easy
LC 2104 — Sum of Subarray Ranges	Medium
LC 316 — Remove Duplicate Letters	Medium
LC 402 — Remove K Digits	Medium
LC 581 — Shortest Unsorted Continuous Subarray	Medium
LC 962 — Maximum Width Ramp	Medium
LC 1019 — Next Greater Node in Linked List	Medium
LC 1124 — Longest Well-Performing Interval	Medium
LC 1130 — Minimum Cost Tree From Leaf Values	Medium
LC 1475 — Final Prices With a Special Discount	Easy
LC 1504 — Count Submatrices With All Ones	Medium
LC 1673 — Find the Most Competitive Subsequence	Medium
LC 1793 — Maximum Score of a Good Subarray	Hard
LC 2289 — Steps to Make Array Non-decreasing	Medium
CC — Stack Operations (STACKOP)	Easy
CC — Histogram Area (HISTAREA)	Medium

---

Related Topics

• Stack — monotonic stack is a specialised stack
• Sliding Window — sliding window maximum uses monotonic deque

← Back to Home · © sparshjaswal