[AlgoMastery]
Topics›Array›Monotonic Stack
📖

Monotonic Stack

Array
~20 min read
5 practice problems

Overview

Monotonic Stack is a stack that maintains elements in monotonic order (either strictly increasing or strictly decreasing). It's used to efficiently find the next/previous greater or smaller element for each position in an array.

The key insight: when processing elements, maintain a stack where elements are ordered. Pop elements that violate the monotonic property, which helps find relationships between elements.

Monotonic stack is particularly useful for:

  • Next greater/smaller element
  • Previous greater/smaller element
  • Largest rectangle in histogram
  • Trapping rain water
  • Stock span problems
  • Remove K digits

Pattern 1: Next Greater Element

Find next greater element for each position.

function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element is greater than stack top
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Circular array:

function nextGreaterElementsCircular(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  
  // Process array twice for circular
  for (let i = 0; i < n * 2; i++) {
    const index = i % n;
    
    while (stack.length > 0 && nums[index] > nums[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      result[top] = nums[index];
    }
    
    if (i < n) {
      stack.push(index);
    }
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 2: Next Smaller Element

Find next smaller element for each position.

function nextSmallerElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element is smaller than stack top
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 3: Previous Greater Element

Find previous greater element for each position.

function previousGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  for (let i = nums.length - 1; i >= 0; i--) {
    // Pop while current element is greater than stack top
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 4: Largest Rectangle in Histogram

Find largest rectangle area in histogram.

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    
    // Pop while current height is smaller
    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;
}

Time: O(n), Space: O(n)

Explanation: For each bar, find how far it can extend left and right (until smaller bar).

Pattern 5: Maximal Rectangle

Find maximal rectangle in binary matrix.

function maximalRectangle(matrix: string[][]): number {
  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++) {
    // Update heights for current row
    for (let j = 0; j < cols; j++) {
      heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
    }
    
    // Find largest rectangle in histogram
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }
  
  return maxArea;
}

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  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;
}

Time: O(rows * cols), Space: O(cols)

Pattern 6: Trapping Rain Water

Calculate trapped rainwater.

function trap(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      
      if (stack.length === 0) break;
      
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const trappedHeight = Math.min(height[i], height[left]) - height[bottom];
      water += width * trappedHeight;
    }
    
    stack.push(i);
  }
  
  return water;
}

Time: O(n), Space: O(n)

Explanation: Stack stores indices of decreasing heights. When taller bar found, calculate trapped water.

Pattern 7: Daily Temperatures

Find days until warmer temperature.

function dailyTemperatures(temperatures: number[]): number[] {
  const result = new Array(temperatures.length).fill(0);
  const stack: number[] = [];
  
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = i - index;
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 8: Remove K Digits

Remove K digits to form smallest number.

function removeKdigits(num: string, k: number): string {
  const stack: string[] = [];
  
  for (const digit of num) {
    // Remove digits that are larger than current
    while (stack.length > 0 && k > 0 && stack[stack.length - 1] > digit) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }
  
  // Remove remaining K digits from end
  while (k > 0 && stack.length > 0) {
    stack.pop();
    k--;
  }
  
  // Remove leading zeros
  while (stack.length > 0 && stack[0] === '0') {
    stack.shift();
  }
  
  return stack.length === 0 ? '0' : stack.join('');
}

Time: O(n), Space: O(n)

Greedy: Remove larger digits from left when possible.

Pattern 9: Stock Span Problem

Calculate stock span (days until price was higher).

class StockSpanner {
  private stack: Array<[number, number]>; // [price, span]
  
  constructor() {
    this.stack = [];
  }
  
  next(price: number): number {
    let span = 1;
    
    // Pop while previous prices are <= current
    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
      span += this.stack.pop()![1];
    }
    
    this.stack.push([price, span]);
    return span;
  }
}

Time: O(1) amortized, Space: O(n)

Pattern 10: Next Greater Element in Array 1

Find next greater element for nums1 in nums2.

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const nextGreater = new Map<number, number>();
  const stack: number[] = [];
  
  // Build next greater map for nums2
  for (const num of nums2) {
    while (stack.length > 0 && num > stack[stack.length - 1]) {
      nextGreater.set(stack.pop()!, num);
    }
    stack.push(num);
  }
  
  // Query for nums1
  return nums1.map(num => nextGreater.get(num) || -1);
}

Time: O(n + m), Space: O(n + m)

Pattern 11: Sum of Subarray Minimums

Sum of minimums of all subarrays.

function sumSubarrayMins(arr: number[]): number {
  const MOD = 1000000007;
  const stack: number[] = [];
  let sum = 0;
  
  for (let i = 0; i <= arr.length; i++) {
    const val = i === arr.length ? 0 : arr[i];
    
    while (stack.length > 0 && val < arr[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      const right = i;
      
      // Count subarrays where arr[index] is minimum
      const count = (index - left) * (right - index);
      sum = (sum + arr[index] * count) % MOD;
    }
    
    stack.push(i);
  }
  
  return sum;
}

Time: O(n), Space: O(n)

Explanation: For each element, count subarrays where it's minimum using left/right boundaries.

Pattern 12: Online Stock Span

Calculate span with online queries.

class OnlineStockSpan {
  private prices: number[];
  private spans: number[];
  
  constructor() {
    this.prices = [];
    this.spans = [];
  }
  
  next(price: number): number {
    let span = 1;
    
    // Look back at previous prices
    let i = this.prices.length - 1;
    while (i >= 0 && this.prices[i] <= price) {
      span += this.spans[i];
      i -= this.spans[i];
    }
    
    this.prices.push(price);
    this.spans.push(span);
    
    return span;
  }
}

Time: O(1) amortized, Space: O(n)

When to Use Monotonic Stack

Use monotonic stack when:

  • Need to find next/previous greater/smaller element
  • Problem involves increasing/decreasing sequences
  • Range queries with min/max constraints
  • Rectangle/histogram area problems
  • Trapping water problems
  • Greedy removal problems

Key insight: Stack maintains order, allowing efficient lookups of relationships between elements.

Template (Monotonic Increasing Stack)

function monotonicIncreasingStack(nums: number[]): number[] {
  const stack: number[] = [];
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element violates monotonic property
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      // Process popped element
      result[index] = nums[i]; // Next smaller element
    }
    stack.push(i);
  }
  
  return result;
}

Template (Monotonic Decreasing Stack)

function monotonicDecreasingStack(nums: number[]): number[] {
  const stack: number[] = [];
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element violates monotonic property
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      // Process popped element
      result[index] = nums[i]; // Next greater element
    }
    stack.push(i);
  }
  
  return result;
}

Time and Space Complexity Summary

  • Next greater/smaller: O(n) time, O(n) space
  • Largest rectangle: O(n) time, O(n) space
  • Trapping rain water: O(n) time, O(n) space
  • Remove K digits: O(n) time, O(n) space
  • Stock span: O(1) amortized time, O(n) space
  • Sum subarray minimums: O(n) time, O(n) space

Practice Tips

  1. Choose order - Increasing vs decreasing stack
  2. Store indices - Usually store indices, not values
  3. Process on pop - Handle popped elements
  4. Boundary handling - Handle empty stack cases
  5. Circular arrays - Process array twice

Common Mistakes

  1. Wrong order - Using increasing when need decreasing
  2. Index vs value - Confusing what to store
  3. Boundary errors - Not handling empty stack
  4. Off-by-one - Width calculation errors
  5. Not processing - Forgetting to handle popped elements

Related Concepts

  • Stack - Core data structure
  • Greedy Algorithm - Often used together
  • Dynamic Programming - Can combine with DP
  • Two Pointers - Alternative for some problems

Monotonic stack is powerful for element relationship problems. Master this technique, and you'll efficiently solve next/previous greater/smaller element problems and related challenges in coding interviews.

← PreviousFrequency CountingNext →Monotonic Queue