Monotonic Stack & Queue

1. Introduction

What are Monotonic Stacks and Queues?

A Monotonic stack or queue is a specialized structure that maintains its elements in a strictly sorted order (either increasing or decreasing) as new elements are added:

A Monotonic Decreasing stack keeps values sorted from largest at the bottom to smallest at the top.

A Monotonic Increasing stack keeps values sorted from smallest at the bottom to largest at the top.

Why is it Important?

Brute force algorithms that search for range limits (e.g. finding the next larger element in an array) take O(N²) time. A monotonic structure resolves this in O(N) time by immediately discarding elements that are blocked or superseded by larger incoming elements.

Where is it Used?

Histogram calculations: Finding the largest rectangle bounded by bar heights.

Stock breakouts: Identifying periods when market values exceed past peaks.

---

2. Mental Model: The Horizon Line

Imagine standing on top of a building and looking to your right:

You see several buildings of varying heights.

If a building is taller than the ones before it, it blocks your view of anything shorter behind it.

Monotonic Decreasing Stack: As you scan right, you keep a list of visible buildings. If you reach a new building X that is taller than the building on top of your list, you pop the top buildings off your list because building X has now blocked them out!

---

3. Core Algorithms & Implementations

1. Next Greater Element I (LeetCode 496)

For each element, find the next element to its right that is larger.

Algorithm: Traverse the array. While the stack is not empty and the current element x is larger than the stack's top element, pop from the stack and record x as their next greater element. Push x onto the stack.

2. Sliding Window Maximum (LeetCode 239)

Find the maximum element inside a sliding window of size K.

Algorithm: Maintain a Monotonic Deque storing element indices.

For each element nums[i], remove indices from the back of the Deque whose values are ≤ nums[i].

Remove indices from the front of the Deque that fall outside the current window boundary [i - K + 1, i].

The index at the front of the Deque always references the maximum element for the current window.

---

4. Visual Trace: Next Greater Element

Tracing input array [2, 1, 5, 3]. Result initialized to [-1, -1, -1, -1]. Stack stores indices.

---

5. Real-World Applications

Stock Chart Breakouts: Calculating the breakout dates where current stock prices surpass all prices in the last K trading days.

Topographic Rain Trapping: Calculating maximum volumes of water trapped between elevation columns.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test range expansion boundaries:

"Given temperatures, return an array of days you have to wait for a warmer day." (Daily Temperatures -> equivalent to Next Greater Element index difference).

"Find the largest rectangular area in a histogram." -> Find the left and right boundary limits for each bar using monotonic stacks.

Common Mistakes

> 2. Wrong Comparison Operators: Using strictly greater > vs greater-equal >= can cause elements with duplicate values to loop or skip boundary checks.

---

7. Summary

Sorted Invariant: Monotonic structures maintain strictly sorted ordering of elements.

Eviction Rule: Discard elements that violate the sorting order when a new element arrives.

Indices: Store indices instead of raw values to preserve distance information.

---

8. Quiz

Question 1: What is the time complexity of Next Greater Element using a monotonic stack?

Answer: O(N) time. Although there is a nested while loop, each index is pushed onto the stack exactly once and popped at most once. The total number of pointer modifications is bounded by 2N, yielding an amortized complexity of O(1) per element.

Question 2: What is the difference between a monotonic increasing and decreasing stack?

Answer:

A monotonic increasing stack is sorted from smallest (bottom) to largest (top). It is used to find the next smaller element.

A monotonic decreasing stack is sorted from largest (bottom) to smallest (top). It is used to find the next larger element.

Question 3: How do we construct a Monotonic Decreasing stack?

Answer: When pushing element x, while stack.peek() < x, pop elements from the stack. Once stack.peek() >= x (or stack is empty), push x.

Question 4: True or False: Monotonic deque for Sliding Window Maximum stores element values directly.

Answer: False. It must store indices so we can identify when the maximum element has slipped outside the active sliding window boundary (index < i - K + 1) and pop it from the front.

Question 5: What is the output of nextGreaterElement([1, 3, 2, 4])?

Answer: [3, 4, 4, -1].