SyntaxShelf

Monotonic stack

2 snippets in Interview Prep

DSAInterview Prep

Next Greater Element (Monotonic Stack)

DSA · Stacks & Queues
Syntax
Traverse from right to left (or left to right).
Maintain a decreasing stack.
For each element, pop smaller elements - the top is the next greater.
Example
// JavaScript
function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = []; // stores indices
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

# Python
def next_greater_elements(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result
Output
next_greater_elements([4, 5, 2, 10, 8]) → [5, 10, 10, -1, -1]

Note Time O(n), Space O(n). Each element is pushed and popped at most once. Used in: stock span, daily temperatures, histogram problems. For circular arrays, iterate through the array twice (use i % n).

Monotonic Stack Pattern

DSA · Stacks & Queues
Syntax
A stack that maintains elements in sorted order (increasing or decreasing).
Before pushing, pop all elements that violate the ordering.
Used for: next greater/smaller, largest rectangle in histogram.
Example
// JavaScript - Largest rectangle in histogram
function largestRectangle(heights) {
  const stack = []; // indices of increasing heights
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i < heights.length ? heights[i] : 0;
    while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

# Python
def largest_rectangle(heights):
    stack = []
    max_area = 0
    for i in range(len(heights) + 1):
        h = heights[i] if i < len(heights) else 0
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area
Output
largest_rectangle([2,1,5,6,2,3]) → 10 (height 5, width 2)

Note Time O(n), Space O(n). The sentinel value (appending 0 at the end) forces all remaining bars to be processed. This is a hard problem but the monotonic stack template is reusable. Variant: maximal rectangle in a binary matrix applies this per row.

Frequently asked questions

How does Interview Prep handle monotonic stack?
Interview Prep covers this with 2 copy-ready snippets on this page. The "Next Greater Element (Monotonic Stack)" snippet in Interview Prep uses `Traverse from right to left (or left to right).`.
Which code does the Interview Prep example use?
The "Next Greater Element (Monotonic Stack)" snippet uses `Traverse from right to left (or left to right).`, from the Stacks & Queues section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "monotonic stack"?
Besides "Next Greater Element (Monotonic Stack)", this page also shows "Monotonic Stack Pattern".
Is there anything to watch out for?
Yes. For "Next Greater Element (Monotonic Stack)": Time O(n), Space O(n). Each element is pushed and popped at most once. Used in: stock span, daily temperatures, histogram problems. For circular arrays, iterate through the array twice (use i % n).

Browse all tasks by intent