A monotonic queue is a deque with an invariant: elements stay sorted (increasing or decreasing) because anything that violates the order is evicted — it can never be the answer.
Focus on recognizing:
“Window max/min” / “next greater/smaller element” → eviction invariant
The Invariant
Decreasing deque (max queries): pop back while back < new
Increasing deque (min queries): pop back while back > new
Front = current answerEviction is permanent and safe: an evicted element is smaller than a NEWER element that outlives it in the window — it will never be queried again.
Pattern 1: Sliding Window Minimum
Minimum of every 3-wide window over [2,1,4,3,6,5] — bigger values die at the back so the smallest lives at the front. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Sliding Window Minimum
Min of every fixed-size window as it slides across an array.
Maintain an increasing deque of indices. Before adding i, drop indices whose value ≥ nums[i] from the back (they can never beat nums[i] as the min) and drop indices that fell out of the window from the front. The front is always the current window minimum. O(n) total.
1
for i in 0..n-1:
2
if deque[0] <= i - k: poll left // out of window
3
while deque[-1] value > nums[i]: pop right
4
push i
5
if i >= k-1: output nums[deque[0]]
public int[] minSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>(); // increasing
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k)
dq.pollFirst(); // expired
while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i])
dq.pollLast(); // break invariant
dq.offerLast(i);
if (i >= k - 1)
result[i - k + 1] = nums[dq.peekFirst()];
}
return result;
}from collections import deque
def min_sliding_window(nums, k):
dq = deque() # increasing
result = []
for i, num in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] > num:
dq.pop() # break invariant
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return resultvector<int> minSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // increasing
vector<int> result;
for (int i = 0; i < (int)nums.size(); i++) {
if (!dq.empty() && dq.front() <= i - k)
dq.pop_front(); // expired
while (!dq.empty() && nums[dq.back()] > nums[i])
dq.pop_back(); // break invariant
dq.push_back(i);
if (i >= k - 1)
result.push_back(nums[dq.front()]);
}
return result;
}function minSlidingWindow(nums, k) {
const dq = []; // increasing
const result = [];
for (let i = 0; i < nums.length; i++) {
if (dq.length && dq[0] <= i - k) dq.shift(); // expired
while (dq.length && nums[dq.at(-1)] > nums[i])
dq.pop(); // break invariant
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}Invariant direction picks the answer end: increasing front = min, decreasing front = max.
Pattern 2: Next Greater Element (Same Skeleton, No Window)
Drop the window, keep the deque — identical resolution logic.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Next Greater Element
For each element, find the next greater element to its right. A decreasing stack holds elements waiting for their answer. When a bigger element arrives, it resolves all smaller ones.
Array: [4,5,2,25]. Decreasing stack of values. Each new element pops everything smaller — those popped elements get the new element as their answer.
1
stack = [] // values waiting for their NGE
2
for x in nums:
3
while stack and x > stack.top:
4
answer[pop()] = x
5
push(x)
6
leftovers → answer = -1
Pop-from-back answers “next greater” as elements are evicted:
public int[] nextGreater(int[] nums) {
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indices
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty()
&& nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i]; // found its answer
}
stack.push(i);
}
return result;
}def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indices, decreasing
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num # found its answer
stack.append(i)
return resultvector<int> nextGreater(vector<int>& nums) {
vector<int> result(nums.size(), -1);
stack<int> st; // indices
for (int i = 0; i < (int)nums.size(); i++) {
while (!st.empty() && nums[st.top()] < nums[i]) {
result[st.top()] = nums[i]; // found its answer
st.pop();
}
st.push(i);
}
return result;
}function nextGreater(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // indices, decreasing
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack.at(-1)] < nums[i]) {
result[stack.pop()] = nums[i]; // found its answer
}
stack.push(i);
}
return result;
}Same monotonic idea minus expiry — no window means no
pollFirstcheck.
What Are We Actually Storing?
Indices — never values:
- Expiry needs positions (
index <= i − k). - Values are one lookup away (
nums[index]). - Equal values: keep or evict consistently — either works if you stay uniform.
Common Mistakes
Mixing up eviction directions.
Max wants < eviction (decreasing), min wants > (increasing). Write the invariant as a comment first.
Expiring after reading the answer.
Remove the expired front BEFORE using peekFirst() as output.
Forgetting leftover candidates.
In next-greater problems, unpopped indices stay -1 — pre-fill the array.
Complexity
| Metric | Value |
|---|---|
| Time | O(n) — each index enters/leaves once |
| Space | O(k) window / O(n) next-greater |
Premium Content
Unlock Monotonic Queue and all premium lessons with a subscription.
From ₹199.99/year — See plans