Monotonic Stack - Complete Guide

A monotonic stack maintains elements in sorted order (increasing or decreasing). It’s powerful for problems involving next greater/smaller elements.

What is a Monotonic Stack? #

A stack that maintains monotonic (either increasing or decreasing) order by removing elements that break the monotonicity.

Types:

  • Monotonic Increasing - Elements increase from bottom to top
  • Monotonic Decreasing - Elements decrease from bottom to top

Use cases:

  • Next greater element
  • Next smaller element
  • Histogram problems
  • Stock span problems

Monotonic Increasing Stack #

Elements increase from bottom to top.

function monotonicIncreasing(nums) {
  const stack = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove smaller elements
    while (stack.length > 0 && stack[stack.length - 1] > nums[i]) {
      stack.pop();
    }

    stack.push(nums[i]);
    result.push([...stack]);
  }

  return result;
}

console.log(monotonicIncreasing([3, 1, 4, 1, 5, 9, 2, 6]));
// [[3], [1], [1, 4], [1], [1, 5], [1, 5, 9], [1, 2], [1, 2, 6]]

Monotonic Decreasing Stack #

Elements decrease from bottom to top.

function monotonicDecreasing(nums) {
  const stack = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove smaller elements
    while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
      stack.pop();
    }

    stack.push(nums[i]);
    result.push([...stack]);
  }

  return result;
}

console.log(monotonicDecreasing([3, 1, 4, 1, 5, 9, 2, 6]));
// [[3], [3, 1], [4], [4, 1], [5], [9], [9, 2], [9, 6]]

Next Greater Element #

Find next greater element for each element.

function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];  // Monotonic decreasing (indices)

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  return result;
}

console.log(nextGreaterElement([2, 1, 2, 4, 3]));
// [4, 2, 4, -1, -1]

Next Greater Element II (Circular) #

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];

  // Traverse twice to handle circular
  for (let i = 0; i < n * 2; i++) {
    const idx = i % n;

    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[idx]) {
      const prevIdx = stack.pop();
      result[prevIdx] = nums[idx];
    }

    if (i < n) {
      stack.push(idx);
    }
  }

  return result;
}

console.log(nextGreaterElements([1, 2, 1]));
// [2, -1, 2]

Next Smaller Element #

function nextSmallerElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];  // Monotonic increasing

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  return result;
}

console.log(nextSmallerElement([4, 8, 5, 2, 25]));
// [2, 5, 2, -1, -1]

Previous Greater Element #

function previousGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];  // Monotonic decreasing

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
      stack.pop();
    }

    if (stack.length > 0) {
      result[i] = nums[stack[stack.length - 1]];
    }

    stack.push(i);
  }

  return result;
}

console.log(previousGreaterElement([4, 5, 2, 10, 8]));
// [-1, -1, 5, -1, 10]

Largest Rectangle in Histogram #

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  let i = 0;

  while (i < heights.length) {
    if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {
      stack.push(i);
      i++;
    } else {
      const top = stack.pop();
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      const area = heights[top] * width;
      maxArea = Math.max(maxArea, area);
    }
  }

  while (stack.length > 0) {
    const top = stack.pop();
    const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
    const area = heights[top] * width;
    maxArea = Math.max(maxArea, area);
  }

  return maxArea;
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]));  // 10

Cleaner Implementation #

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];

    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;
}

Maximal Rectangle #

Find largest rectangle in binary matrix.

function maximalRectangle(matrix) {
  if (matrix.length === 0) return 0;

  const rows = matrix.length;
  const cols = matrix[0].length;
  const heights = new Array(cols).fill(0);
  let maxArea = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === '1') {
        heights[j]++;
      } else {
        heights[j] = 0;
      }
    }

    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }

  return maxArea;
}

const matrix = [
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0']
];

console.log(maximalRectangle(matrix));  // 6

Daily Temperatures #

Days until warmer temperature.

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = [];

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }

  return result;
}

console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]));
// [1, 1, 4, 2, 1, 1, 0, 0]

Stock Span Problem #

Days stock price was less than or equal to today.

function stockSpan(prices) {
  const n = prices.length;
  const span = new Array(n);
  const stack = [];

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
      stack.pop();
    }

    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    stack.push(i);
  }

  return span;
}

console.log(stockSpan([100, 80, 60, 70, 60, 75, 85]));
// [1, 1, 1, 2, 1, 4, 6]

Trapping Rain Water #

function trap(height) {
  const stack = [];
  let water = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop();

      if (stack.length === 0) break;

      const distance = i - stack[stack.length - 1] - 1;
      const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
      water += distance * boundedHeight;
    }

    stack.push(i);
  }

  return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));  // 6

Remove K Digits #

Remove k digits to get smallest number.

function removeKdigits(num, k) {
  const stack = [];

  for (const digit of num) {
    while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }

  // Remove remaining k digits from end
  while (k > 0) {
    stack.pop();
    k--;
  }

  // Remove leading zeros
  while (stack.length > 0 && stack[0] === '0') {
    stack.shift();
  }

  return stack.length === 0 ? '0' : stack.join('');
}

console.log(removeKdigits('1432219', 3));  // '1219'
console.log(removeKdigits('10200', 1));    // '200'
console.log(removeKdigits('10', 2));       // '0'

Sum of Subarray Minimums #

function sumSubarrayMins(arr) {
  const MOD = 1e9 + 7;
  const n = arr.length;
  let result = 0;

  // Find previous less element
  const left = new Array(n);
  const stack = [];

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
      stack.pop();
    }
    left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }

  // Find next less element
  const right = new Array(n);
  stack.length = 0;

  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
      stack.pop();
    }
    right[i] = stack.length === 0 ? n : stack[stack.length - 1];
    stack.push(i);
  }

  // Calculate result
  for (let i = 0; i < n; i++) {
    result = (result + arr[i] * (i - left[i]) * (right[i] - i)) % MOD;
  }

  return result;
}

console.log(sumSubarrayMins([3, 1, 2, 4]));  // 17

Maximum Width Ramp #

function maxWidthRamp(nums) {
  const stack = [];
  const n = nums.length;

  // Build decreasing stack
  for (let i = 0; i < n; i++) {
    if (stack.length === 0 || nums[stack[stack.length - 1]] > nums[i]) {
      stack.push(i);
    }
  }

  let maxWidth = 0;

  // Traverse from right to find max width
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
      maxWidth = Math.max(maxWidth, i - stack.pop());
    }
  }

  return maxWidth;
}

console.log(maxWidthRamp([6, 0, 8, 2, 1, 5]));  // 4

Sliding Window Maximum #

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = [];  // Monotonic decreasing

  for (let i = 0; i < nums.length; i++) {
    // Remove elements outside window
    while (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }

    // Maintain decreasing order
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // Add to result once window is full
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

132 Pattern #

Find i < j < k where nums[i] < nums[k] < nums[j].

function find132pattern(nums) {
  const stack = [];
  let third = -Infinity;

  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < third) {
      return true;
    }

    while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
      third = stack.pop();
    }

    stack.push(nums[i]);
  }

  return false;
}

console.log(find132pattern([1, 2, 3, 4]));     // false
console.log(find132pattern([3, 1, 4, 2]));     // true
console.log(find132pattern([-1, 3, 2, 0]));    // true

Time Complexity #

ProblemTimeSpace
Next GreaterO(n)O(n)
HistogramO(n)O(n)
Daily TemperaturesO(n)O(n)
Trapping Rain WaterO(n)O(n)
Stock SpanO(n)O(n)

Each element pushed/popped at most once.

Pattern Recognition #

Use monotonic stack when:

  • Finding next/previous greater/smaller element
  • Histogram or rectangle problems
  • Temperature or stock span problems
  • Range queries on arrays
  • Subarray min/max problems

Increasing vs Decreasing:

  • Increasing - Find smaller elements
  • Decreasing - Find greater elements

Best Practices #

  1. Choose correct type - Increasing for smaller, decreasing for greater
  2. Store indices - Often needed for distance calculations
  3. Handle boundaries - Add sentinel values if needed
  4. Two passes - Previous and next elements
  5. Deque for sliding window - More flexible than stack
  6. Time is O(n) - Each element processed once
  7. Space is O(n) - Stack size at most n

Monotonic stack is a powerful technique for array problems involving comparisons. Master this pattern to solve many challenging problems efficiently.

Previous Sorting Algorithms - Complete Guide Graph Algorithms - Complete Guide Next