All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Monotonic Stack & Monotonic Queue

Monotonic Stack & Monotonic Queue

0/12 in this phase0/57 across the roadmap

📖 Concept

Monotonic structures maintain elements in sorted order (increasing or decreasing). Elements that violate the order are removed. This pattern solves many "next greater/smaller" and "sliding window extremum" problems in O(n).

Monotonic Stack:

  • Maintain elements in monotonically increasing (or decreasing) order
  • When a new element arrives, pop all elements that violate the ordering
  • Each element is pushed and popped at most once → O(n) total

Use cases:

  • Next Greater Element: For each element, find the first larger element to its right
  • Daily Temperatures: How many days until a warmer day?
  • Largest Rectangle in Histogram: Find the largest rectangle
  • Stock Span: How many consecutive days the stock was ≤ today?

Monotonic Queue (Deque):

  • Maintain elements in monotonically decreasing order (for max)
  • Front of deque is always the maximum in the current window
  • Used for sliding window maximum/minimum in O(n)

🏠 Real-world analogy: Monotonic stack is like a line of people where shorter people behind a tall person leave — only the "stepping stone" heights remain. Monotonic queue is like keeping track of the tallest person visible in a moving window.

💻 Code Example

codeTap to expand ⛶
1// NEXT GREATER ELEMENT — Monotonic decreasing stack
2function nextGreaterElement(nums) {
3  const result = new Array(nums.length).fill(-1);
4  const stack = []; // Stores indices
5

6  for (let i = 0; i < nums.length; i++) {
7    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
8      const idx = stack.pop();
9      result[idx] = nums[i]; // nums[i] is the next greater for nums[idx]
10    }
11    stack.push(i);
12  }
13  return result;
14}
15// [4,5,2,10,8] → [5,10,10,-1,-1]
16

17// DAILY TEMPERATURES
18function dailyTemperatures(temps) {
19  const result = new Array(temps.length).fill(0);
20  const stack = []; // Mono decreasing stack of indices
21

22  for (let i = 0; i < temps.length; i++) {
23    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
24      const idx = stack.pop();
25      result[idx] = i - idx; // Days until warmer
26    }
27    stack.push(i);
28  }
29  return result;
30}
31

32// LARGEST RECTANGLE IN HISTOGRAM — Classic monotonic stack
33function largestRectangleInHistogram(heights) {
34  const stack = []; // Mono increasing stack of indices
35  let maxArea = 0;
36  heights.push(0); // Sentinel to flush remaining
37

38  for (let i = 0; i < heights.length; i++) {
39    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
40      const h = heights[stack.pop()];
41      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
42      maxArea = Math.max(maxArea, h * w);
43    }
44    stack.push(i);
45  }
46  heights.pop(); // Remove sentinel
47  return maxArea;
48}
49

50// SLIDING WINDOW MAXIMUM — Monotonic deque O(n)
51function maxSlidingWindow(nums, k) {
52  const deque = []; // Stores indices, maintains decreasing order of values
53  const result = [];
54

55  for (let i = 0; i < nums.length; i++) {
56    // Remove elements outside window
57    while (deque.length && deque[0] <= i - k) deque.shift();
58    // Remove elements smaller than current (they'll never be max)
59    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
60    deque.push(i);
61    if (i >= k - 1) result.push(nums[deque[0]]); // Front is always max
62  }
63  return result;
64}
65// [1,3,-1,-3,5,3,6,7] k=3 → [3,3,5,5,6,7]

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Next greater element (single array)
  2. Next greater element (circular array)
  3. Daily temperatures
  4. Stock span — how many consecutive days stock ≤ today?
  5. Largest rectangle in histogram
  6. Maximal rectangle in binary matrix
  7. Sliding window maximum
  8. Shortest subarray with sum ≥ k (deque + prefix sum)
  9. Sum of subarray minimums (contribution technique)
  10. Trapping rain water using monotonic stack

⚠️ Common Mistakes

  • Not recognizing the monotonic pattern — keywords: 'next greater', 'next smaller', 'sliding max/min'

  • Storing values in stack instead of indices — indices are needed to compute distances and window bounds

  • Forgetting sentinel values — adding 0 at the end of histogram heights ensures all bars are processed

  • Confusing increasing vs decreasing stack — for 'next greater', use decreasing (pop when element is greater)

  • Not understanding amortized O(n) — each element enters/exits the stack at most once → total O(n)

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Monotonic Stack & Monotonic Queue

← PreviousSkip Lists — Probabilistic Balanced StructureNext →Real-World DSA: Caching Systems (LRU, LFU, TTL)