Monotonic Stack Pattern

When to use Monotonic Stack

• You need the next (or previous) greater or smaller element for every index in an array.
• The problem asks for the largest rectangle, span, or area bounded by heights / temperatures / prices.
• You can phrase the question as 'for each index i, find the closest j with property P' and P is a monotonic comparison.
• A brute-force O(n^2) sweep over every (i, j) pair would TLE, but each element only needs to be 'seen' a constant number of times.
• You are simulating a stack-based parser (valid parentheses, expression evaluation) where order constraints matter.

Template

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

Common mistakes

• Pushing values onto the stack instead of indices, then losing the ability to write the answer back to result[j] when an item pops.
• Using `<=` vs `<` in the comparison without thinking — strict comparison gives the strictly next greater, while non-strict gives the next greater-or-equal, and many problems hinge on this distinction.
• Forgetting the circular wraparound on Next Greater Element II — iterate 2n times and index with i % n so each element sees every other element.
• On Largest Rectangle in Histogram, not appending a sentinel zero (or pretending the array has a virtual zero at the end) to flush remaining items out of the stack.
• Confusing 'next greater on the right' with 'previous greater on the left' — same template, but the iteration direction (and sometimes the comparison sign) flips.