Monotonic Queue
What is a Monotonic Queue
A monotonic queue is a deque that's kept strictly increasing or strictly decreasing from front to back at all times, which makes finding the current maximum or minimum among its elements an O(1) lookup at either end.
Example: What is a Monotonic Queue
#include <iostream>
using namespace std;
int main() {
cout << "Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)");
}
}print("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)")#include <stdio.h>
int main() {
printf("Deque kept strictly increasing or decreasing front-to-back -- max/min at either end is O(1)");
return 0;
}Login to try C/C++/Java code in the editor
Window Maximum
To track the maximum across a sliding window efficiently, a decreasing monotonic deque discards any element from the back that's smaller than the newly arriving one (since it could never be the max again while the new element is still in the window), keeping the true maximum always at the front.
Example: Window Maximum
#include <iostream>
#include <deque>
using namespace std;
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
deque<int> dq;
for (int i = 0; i < 3; i++) {
while (!dq.empty() && arr[dq.back()] < arr[i]) dq.pop_back();
dq.push_back(i);
}
cout << "Max in first window of 3: " << arr[dq.front()];
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < 3; i++) {
while (!dq.isEmpty() && arr[dq.peekLast()] < arr[i]) dq.pollLast();
dq.addLast(i);
}
System.out.println("Max in first window of 3: " + arr[dq.peekFirst()]);
}
}from collections import deque
arr = [1,3,-1,-3,5,3,6,7]
dq = deque()
for i in range(3):
while dq and arr[dq[-1]] < arr[i]:
dq.pop()
dq.append(i)
print("Max in first window of 3:", arr[dq[0]])#include <stdio.h>
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int dq[8], front = 0, back = 0;
for (int i = 0; i < 3; i++) {
while (back > front && arr[dq[back-1]] < arr[i]) back--;
dq[back++] = i;
}
printf("Max in first window of 3: %d", arr[dq[front]]);
return 0;
}Login to try C/C++/Java code in the editor
Window Minimum
The same idea flips for window minimums: an increasing monotonic deque discards elements from the back that are larger than the incoming value, since a bigger element sitting behind a smaller, more recent one can never become the answer.
Example: Window Minimum
#include <iostream>
#include <deque>
using namespace std;
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
deque<int> dq;
for (int i = 0; i < 3; i++) {
while (!dq.empty() && arr[dq.back()] > arr[i]) dq.pop_back();
dq.push_back(i);
}
cout << "Min in first window of 3: " << arr[dq.front()];
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < 3; i++) {
while (!dq.isEmpty() && arr[dq.peekLast()] > arr[i]) dq.pollLast();
dq.addLast(i);
}
System.out.println("Min in first window of 3: " + arr[dq.peekFirst()]);
}
}from collections import deque
arr = [1,3,-1,-3,5,3,6,7]
dq = deque()
for i in range(3):
while dq and arr[dq[-1]] > arr[i]:
dq.pop()
dq.append(i)
print("Min in first window of 3:", arr[dq[0]])#include <stdio.h>
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int dq[8], front = 0, back = 0;
for (int i = 0; i < 3; i++) {
while (back > front && arr[dq[back-1]] > arr[i]) back--;
dq[back++] = i;
}
printf("Min in first window of 3: %d", arr[dq[front]]);
return 0;
}Login to try C/C++/Java code in the editor
Deque Operations
A deque supports adding and removing elements from both its front and back in constant time, which is exactly what this technique needs — new elements enter at the back, and elements that have aged out of the window leave from the front.
Example: Deque Operations
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {2,4,6};
dq.push_back(8); dq.push_front(0); dq.pop_back(); dq.pop_front();
cout << "Add/remove at both ends in O(1): front=" << dq.front() << " back=" << dq.back();
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(2,4,6));
dq.addLast(8); dq.addFirst(0); dq.pollLast(); dq.pollFirst();
System.out.println("Add/remove at both ends in O(1): front=" + dq.peekFirst() + " back=" + dq.peekLast());
}
}from collections import deque
dq = deque([2,4,6])
dq.append(8); dq.appendleft(0); dq.pop(); dq.popleft()
print(f"Add/remove at both ends in O(1): front={dq[0]} back={dq[-1]}")#include <stdio.h>
int main() {
int dq[6] = {0,2,4,6,8,0}, front = 1, back = 5;
back--; front++;
printf("Add/remove at both ends in O(1): front=%d back=%d", dq[front], dq[back-1]);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Because each element is added to the deque exactly once and removed at most once over the whole scan, the total work across the entire array stays O(n), even though a naive recomputation of the window's max at every step would cost far more.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Each element added once, removed at most once over the whole scan -- total work O(n)";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Each element added once, removed at most once over the whole scan -- total work O(n)");
}
}print("Each element added once, removed at most once over the whole scan -- total work O(n)")#include <stdio.h>
int main() {
printf("Each element added once, removed at most once over the whole scan -- total work O(n)");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: