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.