Monotonic Stacks: Next Greater Element & Histogram Area Patterns0%
Queues: FIFO Mechanics, Circular Buffers & Double-Ended Queues (Deque)

Monotonic Stacks: Next Greater Element & Histogram Area Patterns

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Monotonic Stacks: Next Greater Element & Histogram Area Patterns

A Monotonic Stack is a specialized stack whose elements are strictly maintained in a sorted monotonic order—either strictly increasing or strictly decreasing. This pattern is the secret weapon for solving range-lookup problems (like Next Greater Element, Daily Temperatures, and Largest Rectangle in Histogram) in single-pass $O(n)$ linear time instead of brute-force $O(n^2)$.

1. Real-World Analogy: Waiting for a Taller Person

Imagine people standing in a line waiting at a bus stop:

  • A person looks forward into the distance.
  • Shorter people in front of them are completely blocked from view by the first person who is taller than them.
  • Once a giant steps into the line, all shorter people standing behind them are overshadowed. A monotonic decreasing stack maintains this exact line of sight!

2. The Two Types of Monotonic Stacks

  1. 1
    Monotonically Increasing Stack: Elements from bottom to top are in increasing order ($1 \to 3 \to 5 \to 8$).
  • Used to find the Previous/Next Smaller Element.
  1. 1
    Monotonically Decreasing Stack: Elements from bottom to top are in decreasing order ($8 \to 5 \to 3 \to 1$).
  • Used to find the Previous/Next Greater Element.
Output
Algorithm Rule for Monotonic Decreasing Stack (Next Greater Element):
Before pushing element X:
While stack is not empty AND stack.top() < X:
pop() element (because X is the "Next Greater Element" for the popped item!)
push(X)

3. Classic Problem: Daily Temperatures

Given an array of daily temperatures temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i$-th day to get a warmer temperature. If there is no future day with a warmer temperature, keep answer[i] == 0.

Python 3 Implementation:

Python
def daily_temperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
result = [0] * n
stack = [] # Stores INDICES: [index, ...]
for current_day, current_temp in enumerate(temperatures):
# Pop days whose temperatures are cooler than today's temperature!
while stack and temperatures[stack[-1]] < current_temp:
prev_day = stack.pop()
result[prev_day] = current_day - prev_day
stack.append(current_day)
return result

Modern JavaScript / TypeScript Implementation:

TypeScript
export function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const result: number[] = new Array(n).fill(0);
const stack: number[] = []; // Stores indices
 
for (let currentDay = 0; currentDay < n; currentDay++) {
const currentTemp = temperatures[currentDay];
 
while (stack.length > 0 && temperatures[stack[stack.length - 1]] < currentTemp) {
const prevDay = stack.pop()!;
result[prevDay] = currentDay - prevDay;
}
 
stack.push(currentDay);
}
 
return result;
}

4. Trace Table: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Day ($i$)TempStack Before (Indices)While Loop Condition (top_temp < curr)Pops & Result UpdatesStack After
073[]FalseNone[0]
174[0] (73)73 < 74 (True)Pop 0 $\to$ res[0] = 1 - 0 = 1[1]
275[1] (74)74 < 75 (True)Pop 1 $\to$ res[1] = 2 - 1 = 1[2]
371[2] (75)75 < 71 (False)None[2, 3]
469[2, 3] (75, 71)71 < 69 (False)None[2, 3, 4]
572[2, 3, 4] (75, 71, 69)69 < 72, then 71 < 72Pop 4 $\to$ res[4]=1, Pop 3 $\to$ res[3]=2[2, 5]
676[2, 5] (75, 72)72 < 76, then 75 < 76Pop 5 $\to$ res[5]=1, Pop 2 $\to$ res[2]=4[6]
773[6] (76)76 < 73 (False)None[6, 7]

Final Result: [1, 1, 4, 2, 1, 1, 0, 0]. Every index is pushed and popped at most once: $O(n)$ time!

Interactive Quiz

Multiple Choice Questions

Question 1
What is the time complexity of the Monotonic Stack solution for finding the Next Greater Element for all $n$ items in an array?
Question 2
Why do we store the indices of elements on the stack rather than their raw values in problems like Daily Temperatures?
Question 3
What property is maintained by a Monotonically Decreasing Stack?
Question 4
Which advanced algorithmic problem is famously solved in $O(n)$ linear time using a monotonic increasing stack?
Question 5
What is the auxiliary space complexity of a Monotonic Stack for an array of size $n$?
Next Lesson

Queues: FIFO Mechanics, Circular Buffers & Double-Ended Queues (Deque)

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Stacks: LIFO Operations, Array/List Implementations & Bracket MatchingQueues: FIFO Mechanics, Circular Buffers & Double-Ended Queues (Deque)

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext