Monotonic Stack & Queue
Monotonic Stack & Queue
Monotonic Stack and Monotonic Queue are powerful patterns used to solve problems involving next/previous greater or smaller elements and sliding window extremes in O(n) time — problems that would otherwise take O(n²) with brute force.
Video Explanation
🧠 What is a Monotonic Stack?
A Monotonic Stack is a regular stack with one extra rule:
Elements inside the stack are always maintained in a strictly increasing or strictly decreasing order.
When a new element violates this order, we pop elements until the order is restored, then push the new element.
INCREASING Monotonic Stack (bottom → top goes small → large):
Push 3: [3]
Push 5: [3, 5] 5 > 3 ✅ just push
Push 2: pop 5, pop 3 → [2] 2 < 5 ❌ pop until valid, push 2
Push 4: [2, 4] 4 > 2 ✅ just push
Push 1: pop 4, pop 2 → [1] 1 < 4 ❌ pop until valid, push 1
🗂️ Types of Monotonic Stack
| Type | Order | Used For |
|---|---|---|
| Increasing | bottom→top: small→large | Next Smaller Element, Previous Smaller Element, Largest Rectangle |
| Decreasing | bottom→top: large→small | Next Greater Element, Previous Greater Element, Stock Span |
🔍 Classic Problem 1: Next Greater Element
Problem: For each element in the array, find the next element to its right that is greater than it. If none exists, return -1.
Visual Dry-Run
Array: [2, 1, 5, 3, 6, 4]
0 1 2 3 4 5
We use a DECREASING stack (stores indices).
When we find a greater element, it's the answer for everything popped.
i=0: stack=[] → push 0 stack=[0] (val=2)
i=1: arr[1]=1 < arr[0]=2 → push 1 stack=[0,1] (val=2,1)
i=2: arr[2]=5 > arr[1]=1 → pop 1: NGE[1]=5
5 > arr[0]=2 → pop 0: NGE[0]=5
stack empty → push 2 stack=[2] (val=5)
i=3: arr[3]=3 < arr[2]=5 → push 3 stack=[2,3] (val=5,3)
i=4: arr[4]=6 > arr[3]=3 → pop 3: NGE[3]=6
6 > arr[2]=5 → pop 2: NGE[2]=6
stack empty → push 4 stack=[4] (val=6)
i=5: arr[5]=4 < arr[4]=6 → push 5 stack=[4,5] (val=6,4)
End: remaining in stack → NGE = -1
NGE[4]=-1, NGE[5]=-1
✅ Result: [5, 5, 6, 6, -1, -1]
Code Template
- Python
- Java
- C++
def next_greater_element(arr):
n = len(arr)
result = [-1] * n
stack = [] # stores indices
for i in range(n):
# Pop elements smaller than current
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
result[idx] = arr[i] # current element is the NGE
stack.append(i)
# Remaining in stack have no NGE → result stays -1
return result
# Example
arr = [2, 1, 5, 3, 6, 4]
print(next_greater_element(arr)) # Output: [5, 5, 6, 6, -1, -1]
import java.util.Stack;
import java.util.Arrays;
public class MonotonicStack {
public static int[] nextGreaterElement(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>(); // stores indices
for (int i = 0; i < n; i++) {
// Pop elements smaller than current
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
int idx = stack.pop();
result[idx] = arr[i]; // current element is the NGE
}
stack.push(i);
}
// Remaining in stack have no NGE → result stays -1
return result;
}
public static void main(String[] args) {
int[] arr = {2, 1, 5, 3, 6, 4};
System.out.println(Arrays.toString(nextGreaterElement(arr)));
// Output: [5, 5, 6, 6, -1, -1]
}
}
#include <bits/stdc++.h>
using namespace std;
vector<int> nextGreaterElement(vector<int>& arr) {
int n = arr.size();
vector<int> result(n, -1);
stack<int> st; // stores indices
for (int i = 0; i < n; i++) {
// Pop elements smaller than current
while (!st.empty() && arr[st.top()] < arr[i]) {
int idx = st.top();
st.pop();
result[idx] = arr[i]; // current element is the NGE
}
st.push(i);
}
// Remaining in stack have no NGE → result stays -1
return result;
}
int main() {
vector<int> arr = {2, 1, 5, 3, 6, 4};
vector<int> res = nextGreaterElement(arr);
for (int x : res) cout << x << " ";
// Output: 5 5 6 6 -1 -1
return 0;
}
Time Complexity: O(n) — each element is pushed and popped at most once Space Complexity: O(n)
🔍 Classic Problem 2: Previous Smaller Element
Problem: For each element, find the nearest element to its left that is smaller.
Visual Dry-Run
Array: [4, 5, 2, 10, 8]
0 1 2 3 4
We use an INCREASING stack (stores indices).
i=0: stack=[] → push 0 stack=[0] (val=4)
PSE[0] = -1 (stack was empty before push)
i=1: arr[1]=5 > arr[0]=4 → no pop → push 1 stack=[0,1]
PSE[1] = arr[0] = 4
i=2: arr[2]=2 < arr[1]=5 → pop 1
2 < arr[0]=4 → pop 0
stack empty → push 2 stack=[2] (val=2)
PSE[2] = -1 (stack was empty)
i=3: arr[3]=10 > arr[2]=2 → no pop → push 3 stack=[2,3]
PSE[3] = arr[2] = 2
i=4: arr[4]=8 < arr[3]=10 → pop 3
8 > arr[2]=2 → stop → push 4 stack=[2,4]
PSE[4] = arr[2] = 2
✅ Result: [-1, 4, -1, 2, 2]
Code Template
- Python
- Java
- C++
def previous_smaller_element(arr):
n = len(arr)
result = [-1] * n
stack = [] # stores indices
for i in range(n):
# Pop elements greater than or equal to current
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
# Top of stack is the previous smaller element
if stack:
result[i] = arr[stack[-1]]
stack.append(i)
return result
# Example
arr = [4, 5, 2, 10, 8]
print(previous_smaller_element(arr)) # Output: [-1, 4, -1, 2, 2]
import java.util.Stack;
import java.util.Arrays;
public class MonotonicStack {
public static int[] previousSmallerElement(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>(); // stores indices
for (int i = 0; i < n; i++) {
// Pop elements greater than or equal to current
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
stack.pop();
}
// Top of stack is the previous smaller element
if (!stack.isEmpty()) {
result[i] = arr[stack.peek()];
}
stack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] arr = {4, 5, 2, 10, 8};
System.out.println(Arrays.toString(previousSmallerElement(arr)));
// Output: [-1, 4, -1, 2, 2]
}
}
#include <bits/stdc++.h>
using namespace std;
vector<int> previousSmallerElement(vector<int>& arr) {
int n = arr.size();
vector<int> result(n, -1);
stack<int> st; // stores indices
for (int i = 0; i < n; i++) {
// Pop elements greater than or equal to current
while (!st.empty() && arr[st.top()] >= arr[i]) {
st.pop();
}
// Top of stack is the previous smaller element
if (!st.empty()) {
result[i] = arr[st.top()];
}
st.push(i);
}
return result;
}
int main() {
vector<int> arr = {4, 5, 2, 10, 8};
vector<int> res = previousSmallerElement(arr);
for (int x : res) cout << x << " ";
// Output: -1 4 -1 2 2
return 0;
}
Time Complexity: O(n) | Space Complexity: O(n)
🪟 Monotonic Queue (Deque)
A Monotonic Deque is used when you need to efficiently track the maximum or minimum in a sliding window.
Core Idea
Maintain a deque of indices.
- Add new element to BACK (remove smaller elements first for max-deque)
- Remove elements from FRONT if they're outside the window
- Front always holds the index of the MAXIMUM in current window
Window size K=3, Array = [1, 3, -1, -3, 5, 3, 6, 7]
i=0: deque=[0] window=[1] max=1
i=1: 3>1 → pop 0, push 1 deque=[1] window=[1,3] max=3
i=2: -1<3 → push 2 deque=[1,2] window=[1,3,-1] max=3
i=3: -3<-1 → push 3 front=1 in window window=[3,-1,-3] max=3
i=4: 5>all → pop 3,2,1 deque=[4] window=[-1,-3,5] max=5
i=5: 3<5 → push 5 deque=[4,5] window=[-3,5,3] max=5
i=6: 6>3,5 → pop 5,4 deque=[6] window=[5,3,6] max=6
i=7: 7>6 → pop 6 deque=[7] window=[3,6,7] max=7
✅ Result: [3, 3, 5, 5, 6, 7]
Code Template: Sliding Window Maximum
- Python
- Java
- C++
from collections import deque
def sliding_window_maximum(arr, k):
n = len(arr)
result = []
dq = deque() # stores indices, front = index of max
for i in range(n):
# Remove indices outside the window from front
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove indices of smaller elements from back
while dq and arr[dq[-1]] < arr[i]:
dq.pop()
dq.append(i)
# Window is fully formed
if i >= k - 1:
result.append(arr[dq[0]])
return result
# Example
arr = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_maximum(arr, 3)) # Output: [3, 3, 5, 5, 6, 7]
import java.util.ArrayDeque;
import java.util.Deque;
public class MonotonicQueue {
public static int[] slidingWindowMaximum(int[] arr, int k) {
int n = arr.length;
if (n < k) return new int[0];
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
// Remove indices outside the window from front
while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
dq.pollFirst();
}
// Remove indices of smaller elements from back
while (!dq.isEmpty() && arr[dq.peekLast()] < arr[i]) {
dq.pollLast();
}
dq.offerLast(i);
// Window is fully formed
if (i >= k - 1) {
result[i - k + 1] = arr[dq.peekFirst()];
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
int[] res = slidingWindowMaximum(arr, 3);
for (int x : res) System.out.print(x + " ");
// Output: 3 3 5 5 6 7
}
}
#include <bits/stdc++.h>
using namespace std;
vector<int> slidingWindowMaximum(vector<int>& arr, int k) {
int n = arr.size();
vector<int> result;
deque<int> dq; // stores indices
for (int i = 0; i < n; i++) {
// Remove indices outside the window from front
while (!dq.empty() && dq.front() < i - k + 1) {
dq.pop_front();
}
// Remove indices of smaller elements from back
while (!dq.empty() && arr[dq.back()] < arr[i]) {
dq.pop_back();
}
dq.push_back(i);
// Window is fully formed
if (i >= k - 1) {
result.push_back(arr[dq.front()]);
}
}
return result;
}
int main() {
vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7};
vector<int> res = slidingWindowMaximum(arr, 3);
for (int x : res) cout << x << " ";
// Output: 3 3 5 5 6 7
return 0;
}
Time Complexity: O(n) — each element enters and exits deque at most once Space Complexity: O(k)
⚡ Brute Force vs Monotonic Stack
Problem: Next Greater Element for [2, 1, 5, 3, 6, 4]
❌ BRUTE FORCE — O(n²)
For each element, scan all elements to its right:
index 0 (val=2): scan 1,5,3,6,4 → find 5 (5 comparisons)
index 1 (val=1): scan 5,3,6,4 → find 5 (4 comparisons)
index 2 (val=5): scan 3,6,4 → find 6 (3 comparisons)
index 3 (val=3): scan 6,4 → find 6 (2 comparisons)
index 4 (val=6): scan 4 → none (1 comparison)
Total: 15 comparisons
✅ MONOTONIC STACK — O(n)
Each element is pushed once and popped once → max 12 operations
📊 Complexity Summary
| Problem | Time | Space |
|---|---|---|
| Next Greater Element | O(n) | O(n) |
| Previous Smaller Element | O(n) | O(n) |
| Sliding Window Maximum (Deque) | O(n) | O(k) |
| Stock Span Problem | O(n) | O(n) |
| Largest Rectangle in Histogram | O(n) | O(n) |
❌ Common Mistakes
- Using values instead of indices — Always store indices in the stack/deque so you can calculate spans and access original values.
- Wrong pop condition — For Next Greater, pop when
arr[stack.top()] < current. Flipping this gives Next Smaller. - Forgetting remaining stack elements — Elements left in stack after the loop have no NGE → answer is -1.
- Not removing out-of-window indices — In monotonic deque, always check
dq.front() < i - k + 1. - Using Stack for sliding window — Sliding window max needs a Deque (not a stack) because you remove from both ends.
🏋️ Practice Problems
| # | Problem | Pattern | Difficulty |
|---|---|---|---|
| 1 | Next Greater Element I | Monotonic Stack | 🟢 Easy |
| 2 | Next Greater Element II (circular) | Monotonic Stack | 🟡 Medium |
| 3 | Daily Temperatures | Monotonic Stack | 🟡 Medium |
| 4 | Previous Smaller Element | Monotonic Stack | 🟡 Medium |
| 5 | Stock Span Problem | Monotonic Stack | 🟡 Medium |
| 6 | Largest Rectangle in Histogram | Monotonic Stack | 🔴 Hard |
| 7 | Sliding Window Maximum | Monotonic Deque | 🔴 Hard |
| 8 | Shortest Subarray with Sum ≥ K | Monotonic Deque | 🔴 Hard |
🔗 Related Topics
- Two Pointers & Sliding Window: Efficient subarray and window processing techniques ().
- Segment Tree: Dynamic range queries and point/range updates ().
- Disjoint Set Union (DSU): Dynamic graph connectivity and component tracking ().
🔗 References
🧠 Quick Quiz
Test Your Understanding
Answer these 3 questions to check what you have learned.
Q1
What is the main topic of this documentation page?
Q2
What should be identified before implementing monotonic stack queue?
Q3
How is understanding of monotonic stack queue best checked?
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Monotonic Stack & Queue"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.