Monotonic Stack

Maintain a sorted stack to find next/previous greater or smaller elements in O(n).

6 problems 1 Easy 4 Medium 1 Hard

Overview

A monotonic stack keeps elements in sorted order (increasing or decreasing). It is the key insight for problems asking about next/previous greater or smaller elements, and for computing areas in histograms.

When to Use

Largest rectangle in histogram
Trapping rain water
Daily temperatures
Online stock span
Remove k digits

Common Mistakes

Not clearing remaining elements in the stack after the loop
Confusing monotonic increasing vs decreasing for the problem
Using monotonic stack for problems solvable with two pointers

Complexity

Time

O(n) — each element pushed/popped once

Space

O(n)

// Largest Rectangle in Histogram
function largestRectangle(heights) {
  const stack = [-1];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= h) {
      const height = heights[stack.pop()];
      const width = i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Problems (6)

Hide completed

Problem	Difficulty	Companies	Freq
Largest Rectangle in Histogram	Hard	AmazonGoogle +1	High
Next Greater Element I	Easy	Apple	Medium
Sum of Subarray Minimums	Medium	GoogleAmazon	Medium
Online Stock Span	Medium	AmazonMicrosoft	Medium
132 Pattern	Medium	GoogleAmazon +1	Medium
Remove Duplicate Letters	Medium	GoogleLyft	Medium

Monotonic stacks solve next-greater-element and histogram problems in O(n). The pattern, both varian…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee