Monotonic Stack and Queue Patterns

1. Next Greater Element (Stack Pattern)

Concept	Stack Property	Operation	Complexity
Monotonic Stack	Elements in increasing/decreasing order	Pop elements that violate monotonicity	`O(n)`
Next Greater	Decreasing stack (top to bottom)	Pop smaller elements when larger found	`O(n)` amortized
Previous Greater	Same as next greater, scan left to right	Stack top is previous greater	`O(n)`
Circular Array	Process array twice (index % n)	Handle wraparound with modulo	`O(n)`

Example: Next Greater Element

function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // Stores indices
  
  for (let i = 0; i < n; i++) {
    // Pop all smaller elements - current is their next greater
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      const index = stack.pop();
      result[index] = nums[i];
    }
    
    stack.push(i);
  }
  
  // Remaining elements have no next greater (-1)
  return result;
}

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

// Trace:
// i=0, nums[0]=4: stack=[0]
// i=1, nums[1]=5: pop 0 (4<5), result[0]=5, stack=[1]
// i=2, nums[2]=2: stack=[1,2]
// i=3, nums[3]=10: pop 2 (2<10), pop 1 (5<10), result[2]=10, result[1]=10, stack=[3]
// i=4, nums[4]=8: stack=[3,4]
// Final: result[3]=-1, result[4]=-1

Example: Next Greater Element II (Circular Array)

function nextGreaterElementsCircular(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];
  
  // Process array twice to handle circular nature
  for (let i = 0; i < 2 * n; i++) {
    const num = nums[i % n];
    
    while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
      const index = stack.pop();
      result[index] = num;
    }
    
    // Only push indices in first pass
    if (i < n) {
      stack.push(i);
    }
  }
  
  return result;
}

console.log(nextGreaterElementsCircular([1, 2, 1])); // [2, -1, 2]
// In circular: [1,2,1,1,2,1]
// 1 → 2, 2 → -1 (largest), 1 → 2 (wraps around)

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

Example: Next Greater Element I (Subset Problem)

function nextGreaterElementSubset(nums1, nums2) {
  // nums1 is subset of nums2
  const nextGreater = new Map();
  const stack = [];
  
  // Build next greater map for nums2
  for (const num of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < num) {
      nextGreater.set(stack.pop(), num);
    }
    stack.push(num);
  }
  
  // Map nums1 to their next greater in nums2
  return nums1.map(num => nextGreater.get(num) ?? -1);
}

console.log(nextGreaterElementSubset([4, 1, 2], [1, 3, 4, 2]));
// [-, 3, 3]
// 4: no next greater → -1
// 1: next greater is 3
// 2: no next greater → -1

Note: Monotonic stack works in O(n) amortized time because each element is pushed and popped at most once. The stack maintains elements in decreasing order for "next greater" problems.

2. Next Smaller Element Pattern

Variation	Stack Order	Condition	Use Case
Next Smaller	Increasing stack	Pop when current < stack.top()	Find next smaller to the right
Previous Smaller	Increasing stack	Stack top after popping larger	Find previous smaller to the left
Next Greater	Decreasing stack	Pop when current > stack.top()	Find next greater to the right
Previous Greater	Decreasing stack	Stack top after popping smaller	Find previous greater to the left

Example: Next Smaller Element

function nextSmallerElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];
  
  for (let i = 0; i < n; i++) {
    // Pop all greater elements - current is their next smaller
    while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
      const index = stack.pop();
      result[index] = nums[i];
    }
    
    stack.push(i);
  }
  
  return result;
}

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

// Previous and Next for all four variants
function findPrevNextGreaterSmaller(nums) {
  const n = nums.length;
  
  // Next Greater
  const nextGreater = new Array(n).fill(-1);
  let stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      nextGreater[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  
  // Previous Greater
  const prevGreater = new Array(n).fill(-1);
  stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
      stack.pop();
    }
    if (stack.length) prevGreater[i] = nums[stack[stack.length - 1]];
    stack.push(i);
  }
  
  // Next Smaller
  const nextSmaller = new Array(n).fill(-1);
  stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
      nextSmaller[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  
  // Previous Smaller
  const prevSmaller = new Array(n).fill(-1);
  stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
      stack.pop();
    }
    if (stack.length) prevSmaller[i] = nums[stack[stack.length - 1]];
    stack.push(i);
  }
  
  return { nextGreater, prevGreater, nextSmaller, prevSmaller };
}

const arr = [3, 7, 8, 4];
console.log(findPrevNextGreaterSmaller(arr));
// nextGreater:  [7, 8, -1, -1]
// prevGreater:  [-1, -1, -1, 8]
// nextSmaller:  [-1, 4, 4, -1]
// prevSmaller:  [-1, 3, 7, 3]

Monotonic Stack Patterns

Next Greater: Decreasing stack, pop smaller
Next Smaller: Increasing stack, pop greater
Previous Greater: Decreasing stack, check top
Previous Smaller: Increasing stack, check top
Key: Stack order determines what we find

Note: Stack Choice

Decreasing: Find greater elements
Increasing: Find smaller elements
Right scan: Next element
Left scan: Previous element

3. Largest Rectangle in Histogram

Approach	Strategy	Key Insight	Complexity
Monotonic Stack	Track previous/next smaller for each bar	Width = right - left - 1, area = height * width	`O(n)`
Brute Force	For each bar, expand left and right	Find max width with current height	`O(n²)`
Divide & Conquer	Find min in range, recurse left/right	Max is min*width or in subproblem	`O(n log n)`

Example: Largest Rectangle in Histogram

function largestRectangleArea(heights) {
  const stack = []; // Stores indices
  let maxArea = 0;
  
  for (let i = 0; i <= heights.length; i++) {
    // Use 0 as sentinel to pop all remaining bars
    const h = i === heights.length ? 0 : heights[i];
    
    // Pop bars taller than current
    while (stack.length > 0 && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()];
      
      // Width: from element after previous stack top to current-1
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      
      maxArea = Math.max(maxArea, height * width);
    }
    
    stack.push(i);
  }
  
  return maxArea;
}

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

// Trace for [2,1,5,6,2,3]:
// i=0, h=2: stack=[0]
// i=1, h=1: pop 0 (2>1), area=2*1=2, stack=[1]
// i=2, h=5: stack=[1,2]
// i=3, h=6: stack=[1,2,3]
// i=4, h=2: 
//   pop 3 (6>2), area=6*1=6
//   pop 2 (5>2), area=5*2=10 ✓
//   stack=[1,4]
// i=5, h=3: stack=[1,4,5]
// i=6, h=0: pop all, check areas

Example: Using Previous and Next Smaller Arrays

function largestRectangleAreaExplicit(heights) {
  const n = heights.length;
  
  // Find previous smaller (left boundary)
  const prevSmaller = new Array(n).fill(-1);
  let stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
      stack.pop();
    }
    if (stack.length) prevSmaller[i] = stack[stack.length - 1];
    stack.push(i);
  }
  
  // Find next smaller (right boundary)
  const nextSmaller = new Array(n).fill(n);
  stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
      nextSmaller[stack.pop()] = i;
    }
    stack.push(i);
  }
  
  // Calculate max area
  let maxArea = 0;
  for (let i = 0; i < n; i++) {
    const width = nextSmaller[i] - prevSmaller[i] - 1;
    const area = heights[i] * width;
    maxArea = Math.max(maxArea, area);
  }
  
  return maxArea;
}

// Visualization for [2,1,5,6,2,3]:
// Index:        0  1  2  3  4  5
// Heights:      2  1  5  6  2  3
// PrevSmaller: -1 -1  1  2  1  4
// NextSmaller:  1  6  4  4  6  6
// 
// For i=2 (height=5):
//   left = prevSmaller[2] + 1 = 1 + 1 = 2
//   right = nextSmaller[2] - 1 = 4 - 1 = 3
//   width = 3 - 2 + 1 = 2
//   area = 5 * 2 = 10

Example: Maximal Rectangle in Binary Matrix

function maximalRectangle(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  
  const m = matrix.length;
  const n = matrix[0].length;
  const heights = new Array(n).fill(0);
  let maxArea = 0;
  
  for (let row = 0; row < m; row++) {
    // Build histogram heights for current row
    for (let col = 0; col < n; col++) {
      if (matrix[row][col] === '1') {
        heights[col]++;
      } else {
        heights[col] = 0;
      }
    }
    
    // Find largest rectangle in current histogram
    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

// Row 0: heights = [1,0,1,0,0]
// Row 1: heights = [2,0,2,1,1]
// Row 2: heights = [3,1,3,2,2] → max area = 6
// Row 3: heights = [4,0,0,3,0]

Note: For histogram problems, the key insight is: for each bar, find the largest rectangle using this bar as the minimum height. Width is determined by previous and next smaller elements.

4. Sliding Window Maximum (Deque)

Approach	Data Structure	Property	Complexity
Monotonic Deque	Deque storing decreasing values	Front always has max in current window	`O(n)`
Brute Force	Scan window for max each time	Check all k elements per window	`O(n*k)`
Heap/Priority Queue	Max heap with lazy deletion	Extract max, ignore out-of-window	`O(n log k)`

Example: Sliding Window Maximum Using Deque

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // Stores indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove elements outside current window
    while (deque.length && deque[0] < i - k + 1) {
      deque.shift();
    }
    
    // Remove elements smaller than current (they can't be max)
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add max of current window to result
    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]

// Trace for k=3:
// i=0: deque=[0], window=[1]
// i=1: remove 0 (1<3), deque=[1], window=[1,3]
// i=2: deque=[1,2], window=[1,3,-1], max=3
// i=3: deque=[1,3], window=[3,-1,-3], max=3
// i=4: remove 1,2,3 (all<5), deque=[4], window=[-1,-3,5], max=5
// i=5: deque=[4,5], window=[-3,5,3], max=5
// i=6: remove 4,5 (all<6), deque=[6], window=[5,3,6], max=6
// i=7: remove 6 (6<7), deque=[7], window=[3,6,7], max=7

Example: Min and Max in Sliding Window

function minMaxSlidingWindow(nums, k) {
  const maxResult = [];
  const minResult = [];
  const maxDeque = []; // Decreasing deque for max
  const minDeque = []; // Increasing deque for min
  
  for (let i = 0; i < nums.length; i++) {
    // Remove out-of-window elements
    while (maxDeque.length && maxDeque[0] < i - k + 1) maxDeque.shift();
    while (minDeque.length && minDeque[0] < i - k + 1) minDeque.shift();
    
    // Maintain decreasing deque for max
    while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] < nums[i]) {
      maxDeque.pop();
    }
    
    // Maintain increasing deque for min
    while (minDeque.length && nums[minDeque[minDeque.length - 1]] > nums[i]) {
      minDeque.pop();
    }
    
    maxDeque.push(i);
    minDeque.push(i);
    
    if (i >= k - 1) {
      maxResult.push(nums[maxDeque[0]]);
      minResult.push(nums[minDeque[0]]);
    }
  }
  
  return { max: maxResult, min: minResult };
}

console.log(minMaxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// max: [3, 3, 5, 5, 6, 7]
// min: [-1, -3, -3, -3, 3, 3]

Note: Monotonic deque maintains a decreasing sequence of indices for max (increasing for min). Front has the maximum, back removes smaller elements that can never be maximum.

5. Stock Span Problem

Concept	Definition	Approach	Complexity
Stock Span	Number of consecutive days ≤ current price	Count days from current back to previous greater	`O(n)`
Monotonic Stack	Store indices of decreasing prices	Span = current index - previous greater index	`O(n)`
Brute Force	For each day, scan backwards	Count until price > current	`O(n²)`

Example: Stock Span

function calculateSpan(prices) {
  const n = prices.length;
  const span = new Array(n);
  const stack = []; // Stores indices
  
  for (let i = 0; i < n; i++) {
    // Pop all prices less than or equal to current
    while (stack.length && prices[stack[stack.length - 1]] <= prices[i]) {
      stack.pop();
    }
    
    // Span = distance to previous greater (or start of array)
    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    
    stack.push(i);
  }
  
  return span;
}

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

// Explanation:
// Day 0 (100): no previous days, span=1
// Day 1 (80): 80<100, span=1
// Day 2 (60): 60<80, span=1
// Day 3 (70): 70>60, includes day 2, span=2
// Day 4 (60): 60<70, span=1
// Day 5 (75): 75>60,60,70,60, includes days 2-4, span=4
// Day 6 (85): 85>75,60,70,60,80, includes days 1-5, span=6

Example: Online Stock Span (Class Design)

class StockSpanner {
  constructor() {
    this.stack = []; // [price, span]
    this.index = 0;
  }
  
  next(price) {
    let span = 1;
    
    // Pop all lower or equal prices and accumulate their spans
    while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
      span += this.stack.pop()[1];
    }
    
    this.stack.push([price, span]);
    return span;
  }
}

const spanner = new StockSpanner();
console.log(spanner.next(100)); // 1
console.log(spanner.next(80));  // 1
console.log(spanner.next(60));  // 1
console.log(spanner.next(70));  // 2
console.log(spanner.next(60));  // 1
console.log(spanner.next(75));  // 4
console.log(spanner.next(85));  // 6

// Alternative: Store with indices
class StockSpannerWithIndex {
  constructor() {
    this.stack = []; // [index, price]
    this.index = -1;
  }
  
  next(price) {
    this.index++;
    
    while (this.stack.length && this.stack[this.stack.length - 1][1] <= price) {
      this.stack.pop();
    }
    
    const span = this.stack.length === 0 
      ? this.index + 1 
      : this.index - this.stack[this.stack.length - 1][0];
    
    this.stack.push([this.index, price]);
    return span;
  }
}

6. Trapping Rain Water Problem

Approach	Strategy	Key Insight	Complexity
Two Pointers	Track left_max and right_max	Water = min(left_max, right_max) - height	`O(n)`, O(1) space
Monotonic Stack	Calculate horizontal layers	Fill by height differences	`O(n)`, O(n) space
DP Arrays	Precompute left_max and right_max	Two passes to build arrays	`O(n)`, O(n) space

Example: Trapping Rain Water (Two Pointers)

function trap(height) {
  if (!height.length) return 0;
  
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  
  while (left < right) {
    if (height[left] < height[right]) {
      // Process left side
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      // Process right side
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  
  return water;
}

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

// Visualization:
//     ██
// ██▓▓██▓██
// ██▓███▓███
// Water (▓) = 6 units

Example: Trapping Rain Water (Monotonic Stack)

function trapStack(height) {
  const stack = []; // Stores indices
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    // Fill water when we find a taller bar
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop();
      
      if (!stack.length) 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;
}

// DP approach with precomputed arrays
function trapDP(height) {
  const n = height.length;
  if (n === 0) return 0;
  
  const leftMax = new Array(n);
  const rightMax = new Array(n);
  
  // Build left max array
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }
  
  // Build right max array
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }
  
  // Calculate water
  let water = 0;
  for (let i = 0; i < n; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  
  return water;
}

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

Example: Trapping Rain Water II (2D Grid)

function trapRainWater2D(heightMap) {
  if (!heightMap.length || !heightMap[0].length) return 0;
  
  const m = heightMap.length;
  const n = heightMap[0].length;
  
  // Min heap: [height, row, col]
  const pq = new MinHeap((a, b) => a[0] - b[0]);
  const visited = Array(m).fill(null).map(() => Array(n).fill(false));
  
  // Add all border cells to heap
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
        pq.push([heightMap[i][j], i, j]);
        visited[i][j] = true;
      }
    }
  }
  
  const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
  let water = 0;
  let maxHeight = 0;
  
  while (pq.size() > 0) {
    const [height, row, col] = pq.pop();
    maxHeight = Math.max(maxHeight, height);
    
    for (const [dr, dc] of dirs) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (newRow >= 0 && newRow < m && 
          newCol >= 0 && newCol < n && 
          !visited[newRow][newCol]) {
        
        visited[newRow][newCol] = true;
        
        // Water trapped = max seen height - current height
        if (heightMap[newRow][newCol] < maxHeight) {
          water += maxHeight - heightMap[newRow][newCol];
        }
        
        pq.push([heightMap[newRow][newCol], newRow, newCol]);
      }
    }
  }
  
  return water;
}

// Helper MinHeap class (reuse from previous sections)
class MinHeap {
  constructor(compareFn) {
    this.heap = [];
    this.compare = compareFn || ((a, b) => a - b);
  }
  
  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }
  
  bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.compare(this.heap[p], this.heap[i]) <= 0) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }
  
  bubbleDown(i) {
    while (true) {
      let min = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < this.size() && this.compare(this.heap[left], this.heap[min]) < 0) min = left;
      if (right < this.size() && this.compare(this.heap[right], this.heap[min]) < 0) min = right;
      if (min === i) break;
      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }
  }
  
  size() { return this.heap.length; }
}

Note: For trapping rain water, the key insight is: water at position i = min(leftMax, rightMax) - height[i]. Two pointers optimize space by tracking maxes on-the-fly without extra arrays.

Summary: Monotonic Stack Queue Pattern

Next Greater Element: Decreasing stack - pop smaller when larger found - O(n) amortized
Next Smaller Element: Increasing stack - pop greater when smaller found - mirror of next greater
Largest Rectangle: For each bar, find previous/next smaller - width between them, area = height * width
Sliding Window Max: Monotonic deque (decreasing) - front is max, remove out-of-window from front
Stock Span: Days since last greater price - use stack to track previous greater index
Trapping Rain Water: Two pointers with leftMax/rightMax - water = min(maxes) - height
Stack vs Deque: Stack for next/previous elements, Deque for sliding window max/min
Monotonic Property: Decreasing for greater, increasing for smaller - maintains order invariant
Key Insight: Each element pushed and popped once - amortized O(n) despite nested loops

Related Cheat Sheets

Algorithm Patterns