Monotonic stack

Next Greater Element (Monotonic Stack)

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.

DSAInterview Prep