🗂️Data StructureIntermediate

Monotonic Deque

Key Points

•
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).
•
It enables O(1) amortized time per push/pop by removing dominated elements only once and evicting outdated indices from the front.
•
The classic use is sliding window maximum or minimum in O(n), far faster than the naive O(nk) per k-sized window.
•
For shortest subarray with sum at least K, maintain an increasing deque of prefix sums to efficiently find minimal lengths.
•
With two pointers, two monotonic deques can maintain window min and max to enforce constraints like max − $min \leq l imi t$ .
•
Each index is pushed at most once and popped at most once, giving total O(n) operations over the whole pass.
•
Store indices (not just values) to know when an element leaves the window and to compare correct positions.
•
Choose decreasing order for maximum queries and increasing order for minimum queries to keep the best candidate at the front.

Prerequisites

→Arrays and indexing — Monotonic deques store and compare array indices to manage window membership.
→Big-O and amortized analysis — Understanding why each element is pushed and popped at most once explains O(n) total time.
→Deques and queues — Knowledge of basic double-ended operations is necessary to implement the pattern.
→Sliding window and two pointers — The technique is applied while moving a window across the array.
→Prefix sums — Required for problems like shortest subarray with sum at least K.
→Comparators and order properties — Knowing when to maintain increasing vs decreasing order avoids logic bugs.

Detailed Explanation

Tap terms for definitions

01Overview

A monotonic deque is a small but powerful data structure pattern built on top of a standard double-ended queue (deque). The idea is to maintain elements in either nonincreasing (decreasing) or nondecreasing (increasing) order while scanning an array with a sliding window. Because the deque is monotonic, its front is always the best candidate for certain queries—like the maximum or minimum within the current window—so we can answer these queries in O(1) time. The trick is to evict elements that can never influence future answers: any element that is worse and newer than the one you’re inserting is removed from the back, and any element that has left the window is removed from the front. This structure shines in problems where you need to repeatedly compute a window aggregate that respects an order, such as maximum, minimum, or constraints expressed via prefix sums. Classic examples include sliding window maximum/minimum, shortest subarray with sum at least K, and longest subarray where max − min ≤ limit. In all these, the deque provides a single pass O(n) solution. The amortized efficiency arises because each array index enters and leaves the deque at most once. By organizing the deque carefully and maintaining simple invariants, we convert seemingly expensive repeated computations into linear-time scans.

02Intuition & Analogies

Imagine you are watching cars driving by and you want to always know the tallest truck currently in view through a window of k meters. As a new truck arrives (we slide the window forward), you compare it to smaller trucks that arrived just before it; any smaller truck behind the new, taller one cannot ever be the tallest while the tall one is still in view, so you forget about those smaller trucks. This act of forgetting keeps your list of candidate tallest trucks short and ordered from tallest at the front to shorter at the back. When the window advances and an old truck exits the view, if that truck was at the front, you simply remove it and the next best candidate becomes the tallest. You never reconsider a truck you have already discarded because you only discard it when a better truck that lasts longer arrives. This is exactly what a monotonic deque does. The deque holds indices of candidate elements in a helpful order: decreasing for maximums (front is always the largest) or increasing for minimums (front is always the smallest). When a new element arrives, we pop from the back while the new element is better (e.g., larger for max). When the window slides and an index becomes too old (falls out of the left side), we pop it from the front. For prefix-sum problems like shortest subarray with sum ≥ K, think of collecting timestamps of your cumulative distance walked. You want the earliest timestamp that makes the current distance jump by at least K. If a newer timestamp doesn’t improve your chances (its cumulative is not smaller), you drop it from the back; the front keeps the most promising earliest candidates.

03Formal Definition

A monotonic deque D over an array a of length n is a deque that stores a subset of indices in strictly increasing order of indices and maintains a monotonicity invariant on their corresponding values. For a decreasing deque (used for maximum queries), we maintain

a_{D [0]}

\geq

a_{D [1]}

\geq

\dots

\geq

a_{D [∣ D ∣ - 1]}

. For an increasing deque (for minimum queries), we maintain

a_{D [0]}

\leq

a_{D [1]}

\leq

\dots

\leq

a_{D [∣ D ∣ - 1]}

. On arriving index i, we remove indices from the back while they are dominated by i (e.g., for max: while

a_{D . ba c k]}

\leq

a_{i}

, po

p_{b} a c k

), then pus

h_{b} a c k

(i). To keep only the current sliding window [L, R], we remove from the front while D.

f ro n t < L

. The key invariant ensures that the front of D yields the correct aggregate for order-statistics queries within the current window: for a decreasing deque,

a_{D . f ro n t}

max

a_{j}

: j

\in

[L, R] \}. Each index is inserted once and removed at most once because it is either evicted when it ages out (front) or dominated by a later element (back). Therefore, across a full pass of the array, the total number of deque operations is O(n). By choosing the monotonic direction appropriately and storing indices (not just values), the structure supports constant-time access to the current optimum and constant-amortized-time updates while sliding the window.

04When to Use

Use a monotonic deque whenever you repeatedly need the minimum or maximum over a sliding window as you move a pointer across an array. This covers classic tasks like sliding window maximum/minimum over fixed-size windows, computing rolling range (max − min), or checking constraints such as maintaining max − min ≤ limit while expanding and contracting a window with two pointers. It is also ideal when the decision to keep or discard elements can be determined by a total order and local dominance, so that worse, newer elements can be safely popped from the back. For prefix-sum constraints like the shortest subarray with sum at least K, maintain a deque of prefix indices in increasing order of prefix values; this enables you to quickly remove unhelpful candidates and to find the earliest index that satisfies the sum condition with the current prefix. Choose this technique when the naive approach would recompute window aggregates in O(k) per step, but the aggregate is order-based (not something like a median). Avoid it when the query is not order-preserving (e.g., median, mode) or when updates are not simple left-to-right scans. It is especially effective in one-pass, online problems with static arrays and no arbitrary deletions except those naturally caused by the window slide.

⚠️Common Mistakes

Not storing indices: If you store values only, you cannot tell whether the value at the front has fallen out of the window. Always store indices (and use them to check age), then read values by a[index].
Forgetting to evict outdated elements: When i is the current right end, any index ≤ i − k belongs to the previous window. If you forget to pop from the front when D.front ≤ i − k, the front may be outside, giving wrong answers.
Wrong monotonic direction: For maximum queries, the deque must be decreasing so the front is largest; for minimum queries, it must be increasing. Mixing these up yields incorrect results.
Mishandling ties: Decide whether to use strict or non-strict inequality when popping from the back. For sliding maximum, pop while a[back] ≤ a[i] to prefer the newer equal element (it lives longer). Using < instead of ≤ can keep redundant older equals and cause stale fronts.
Off-by-one in window indexing: For 0-based arrays and window size k, the first full window ends at i = k − 1. Eviction condition is while D.front ≤ i − k. Confusing i − k with i − k + 1 is a common bug.
Mixing two-pointers without syncing deques: When contracting the window from the left, be sure to pop fronts whose index equals the leaving left pointer. Forgetting this lets invalid elements linger.
Applying monotonic deque to non-order-friendly aggregates: It doesn’t solve medians, modes, or sums directly (except via prefix-sum tricks). Use alternative structures (heaps, hash maps, or order-statistic trees) for those.

Key Formulas

Amortized Operations Bound

i = 1 \sum n (push_{i} + pop_{i}) \leq 2 n

Explanation: Each index is pushed once and popped at most once from the deque. Summing over all steps gives at most 2n deque operations, implying total O(n) time.

Monotonic Invariant (Max)

a_{D [0]} \geq a_{D [1]} \geq \dots \geq a_{D [∣ D ∣ - 1]} (decreasing deque)

Explanation: Values at stored indices are nonincreasing from front to back. This guarantees that the front always holds the current maximum in the window.

Monotonic Invariant (Min)

a_{D [0]} \leq a_{D [1]} \leq \dots \leq a_{D [∣ D ∣ - 1]} (increasing deque)

Explanation: Values at stored indices are nondecreasing from front to back. This ensures the front always holds the current minimum in the window.

Window Eviction Rule

D . front \leq i - k \Rightarrow D . pop_front ()

Explanation: If the index at the front is older than the left boundary of the current window ending at i, it must be removed because it is no longer inside the window.

Prefix Sum Subarray Condition

P [j] - P [i] \geq K \Leftrightarrow t = i \sum j - 1 a_{t} \geq K

Explanation: The sum of a subarray a[i..j-1] is the difference of prefix sums. To find a shortest subarray with sum at least K, maintain candidate i with increasing P[i].

Potential Method for Amortized Analysis

\overset{c}{^}_{t} = c_{t} + Φ_{t} - Φ_{t - 1}, Φ_{t} = ∣ D_{t} ∣

Explanation: Let the potential be the deque size. Push may increase potential, but future pops decrease it. The amortized cost per step becomes O(1) because total potential change telescopes.

Sliding Window Optimization

O (nk) \to O (n)

Explanation: Naively recomputing a k-window max/min costs O(k) per step, totaling O(nk). Using a monotonic deque reduces this to a single pass O(n).

Complexity Analysis

For sliding window max/min, each index i is pushed into the deque once. It may be popped from the back only when a strictly better or equal element arrives (for max: a[new] ≥ a[old]). Such a pop happens at most once per index because once removed, an index never re-enters. It may also be popped from the front at most once when it leaves the window. Therefore the total number of deque operations over the entire scan is at most 2n, and the time complexity is O(n). Access to the current answer is O(1) by reading the value at the front index. Space complexity is O(k) for fixed-size windows because the deque stores at most k indices at any time. For the shortest subarray with sum at least K, we process n + 1 prefix sums. We maintain an increasing deque of prefix indices: each index is inserted once, and may be popped from the back when a newer prefix is smaller (dominated) or from the front when it enables an answer with the current prefix j (i.e., P[j] − P[front] ≥ K). Again, each index is removed at most once from each side, so the total time remains O(n). Space complexity is O(n) due to storing prefix sums and the deque of indices in the worst case. In two-pointers problems with constraints like max −

min \leq l imi t

, we maintain two deques (one decreasing for max and one increasing for min). Each element enters and leaves each deque at most once, so overall time is O(n), and extra space is O(n) in the worst case, though typically O(k) relating to the active window.

Code Examples

Sliding Window Maximum (Decreasing Monotonic Deque)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Returns the maximum of each window of size k in O(n)
5 vector<int> maxSlidingWindow(const vector<int>& a, int k) {
6     int n = (int)a.size();
7     vector<int> ans;
8     if (k <= 0 || n == 0) return ans;
9     deque<int> dq; // stores indices; values are decreasing from front to back
10     for (int i = 0; i < n; ++i) {
11         // Remove dominated elements from the back (keep deque decreasing)
12         while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
13         dq.push_back(i);
14         // Evict elements that are out of the window (older than i - k + 1)
15         if (dq.front() <= i - k) dq.pop_front();
16         // Record answer once the first full window is formed
17         if (i >= k - 1) ans.push_back(a[dq.front()]);
18     }
19     return ans;
20 }
21 
22 int main() {
23     vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
24     int k = 3;
25     vector<int> res = maxSlidingWindow(a, k);
26     for (int x : res) cout << x << ' ';
27     cout << '\n';
28     return 0;
29 }
30

Maintain a decreasing deque of indices so the front is always the maximum in the current window. For each new index i, pop smaller or equal values from the back, push i, evict front if it leaves the window, and output a[dq.front()].

Time: O(n)Space: O(k)

Sliding Window Minimum (Increasing Monotonic Deque) + Reusable Wrapper

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // A small reusable monotonic deque wrapper storing indices
5 struct MonoDeque {
6     // if dec is true: keep values decreasing (for max). else: keep increasing (for min)
7     bool dec;
8     const vector<int>* arr; // pointer to array for value access
9     deque<int> dq;
10     MonoDeque(bool decreasing, const vector<int>& a) : dec(decreasing), arr(&a) {}
11     // push index i while maintaining monotonicity
12     void push(int i) {
13         if (dec) {
14             while (!dq.empty() && (*arr)[dq.back()] <= (*arr)[i]) dq.pop_back();
15         } else {
16             while (!dq.empty() && (*arr)[dq.back()] >= (*arr)[i]) dq.pop_back();
17         }
18         dq.push_back(i);
19     }
20     // evict indices smaller than left (out of window)
21     void evict_left(int left) {
22         while (!dq.empty() && dq.front() < left) dq.pop_front();
23     }
24     // current best value at the front
25     int best_value() const { return (*arr)[dq.front()]; }
26 };
27 
28 vector<int> minSlidingWindow(const vector<int>& a, int k) {
29     int n = (int)a.size();
30     vector<int> ans;
31     if (k <= 0 || n == 0) return ans;
32     MonoDeque md(false, a); // increasing for minimum
33     for (int i = 0; i < n; ++i) {
34         md.push(i);
35         md.evict_left(i - k + 1);
36         if (i >= k - 1) ans.push_back(md.best_value());
37     }
38     return ans;
39 }
40 
41 int main() {
42     vector<int> a = {4, 2, 12, 3, -1, 6, 8};
43     int k = 3;
44     vector<int> res = minSlidingWindow(a, k);
45     for (int x : res) cout << x << ' ';
46     cout << '\n';
47     return 0;
48 }
49

This demonstrates an increasing monotonic deque for window minimum and shows a reusable wrapper. Elements leaving the window are evicted from the front by index, and dominated elements are removed from the back.

Time: O(n)Space: O(k)

Shortest Subarray With Sum At Least K (Prefix Sums + Increasing Deque)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int shortestSubarrayAtLeastK(const vector<int>& a, long long K) {
5     int n = (int)a.size();
6     vector<long long> P(n + 1, 0);
7     for (int i = 0; i < n; ++i) P[i + 1] = P[i] + a[i];
8     deque<int> dq; // stores indices of prefix sums, increasing by P[index]
9     int ans = n + 1;
10     for (int j = 0; j <= n; ++j) {
11         // While current prefix allows a valid subarray with the earliest candidate, update answer
12         while (!dq.empty() && P[j] - P[dq.front()] >= K) {
13             ans = min(ans, j - dq.front());
14             dq.pop_front();
15         }
16         // Maintain increasing order of prefix sums; drop worse (larger or equal) tails
17         while (!dq.empty() && P[j] <= P[dq.back()]) dq.pop_back();
18         dq.push_back(j);
19     }
20     return ans <= n ? ans : -1;
21 }
22 
23 int main() {
24     vector<int> a = {2, -1, 2};
25     long long K = 3;
26     cout << shortestSubarrayAtLeastK(a, K) << '\n';
27     return 0;
28 }
29

Compute prefix sums P. Maintain a deque of indices with increasing P-values. For each j, pop from the front while P[j] − P[front] ≥ K to update the minimal length; pop from the back while P[j] ≤ P[back] to keep only promising candidates. This yields O(n).

Time: O(n)Space: O(n)

Longest Subarray With Absolute Difference Between Max and Min ≤ limit (Two Deques + Two Pointers)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int longestSubarrayWithinLimit(const vector<int>& a, int limit) {
5     int n = (int)a.size();
6     deque<int> dqMax; // decreasing by value
7     deque<int> dqMin; // increasing by value
8     int L = 0, ans = 0;
9     for (int R = 0; R < n; ++R) {
10         // Insert a[R] into both deques with proper monotonicity
11         while (!dqMax.empty() && a[dqMax.back()] <= a[R]) dqMax.pop_back();
12         dqMax.push_back(R);
13         while (!dqMin.empty() && a[dqMin.back()] >= a[R]) dqMin.pop_back();
14         dqMin.push_back(R);
15         // Shrink from the left until the constraint is satisfied
16         while (!dqMax.empty() && !dqMin.empty() && a[dqMax.front()] - a[dqMin.front()] > limit) {
17             if (dqMax.front() == L) dqMax.pop_front();
18             if (dqMin.front() == L) dqMin.pop_front();
19             ++L;
20         }
21         ans = max(ans, R - L + 1);
22     }
23     return ans;
24 }
25 
26 int main() {
27     vector<int> a = {8, 2, 4, 7};
28     int limit = 4;
29     cout << longestSubarrayWithinLimit(a, limit) << '\n'; // Expected 2
30     return 0;
31 }
32

Maintain two deques: a decreasing one for the current maximum and an increasing one for the current minimum. Expand the right boundary, then move the left boundary forward while max − min exceeds the limit. The answer is the largest valid window length observed.

Time: O(n)Space: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Returns the maximum of each window of size k in O(n)
5	vector<int> maxSlidingWindow(const vector<int>& a, int k) {
6	int n = (int)a.size();
7	vector<int> ans;
8	if (k <= 0 \|\| n == 0) return ans;
9	deque<int> dq; // stores indices; values are decreasing from front to back
10	for (int i = 0; i < n; ++i) {
11	// Remove dominated elements from the back (keep deque decreasing)
12	while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
13	dq.push_back(i);
14	// Evict elements that are out of the window (older than i - k + 1)
15	if (dq.front() <= i - k) dq.pop_front();
16	// Record answer once the first full window is formed
17	if (i >= k - 1) ans.push_back(a[dq.front()]);
18	}
19	return ans;
20	}
21
22	int main() {
23	vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
24	int k = 3;
25	vector<int> res = maxSlidingWindow(a, k);
26	for (int x : res) cout << x << ' ';
27	cout << '\n';
28	return 0;
29	}
30

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// A small reusable monotonic deque wrapper storing indices
5	struct MonoDeque {
6	// if dec is true: keep values decreasing (for max). else: keep increasing (for min)
7	bool dec;
8	const vector<int>* arr; // pointer to array for value access
9	deque<int> dq;
10	MonoDeque(bool decreasing, const vector<int>& a) : dec(decreasing), arr(&a) {}
11	// push index i while maintaining monotonicity
12	void push(int i) {
13	if (dec) {
14	while (!dq.empty() && (arr)[dq.back()] <= (arr)[i]) dq.pop_back();
15	} else {
16	while (!dq.empty() && (arr)[dq.back()] >= (arr)[i]) dq.pop_back();
17	}
18	dq.push_back(i);
19	}
20	// evict indices smaller than left (out of window)
21	void evict_left(int left) {
22	while (!dq.empty() && dq.front() < left) dq.pop_front();
23	}
24	// current best value at the front
25	int best_value() const { return (*arr)[dq.front()]; }
26	};
27
28	vector<int> minSlidingWindow(const vector<int>& a, int k) {
29	int n = (int)a.size();
30	vector<int> ans;
31	if (k <= 0 \|\| n == 0) return ans;
32	MonoDeque md(false, a); // increasing for minimum
33	for (int i = 0; i < n; ++i) {
34	md.push(i);
35	md.evict_left(i - k + 1);
36	if (i >= k - 1) ans.push_back(md.best_value());
37	}
38	return ans;
39	}
40
41	int main() {
42	vector<int> a = {4, 2, 12, 3, -1, 6, 8};
43	int k = 3;
44	vector<int> res = minSlidingWindow(a, k);
45	for (int x : res) cout << x << ' ';
46	cout << '\n';
47	return 0;
48	}
49

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	int shortestSubarrayAtLeastK(const vector<int>& a, long long K) {
5	int n = (int)a.size();
6	vector<long long> P(n + 1, 0);
7	for (int i = 0; i < n; ++i) P[i + 1] = P[i] + a[i];
8	deque<int> dq; // stores indices of prefix sums, increasing by P[index]
9	int ans = n + 1;
10	for (int j = 0; j <= n; ++j) {
11	// While current prefix allows a valid subarray with the earliest candidate, update answer
12	while (!dq.empty() && P[j] - P[dq.front()] >= K) {
13	ans = min(ans, j - dq.front());
14	dq.pop_front();
15	}
16	// Maintain increasing order of prefix sums; drop worse (larger or equal) tails
17	while (!dq.empty() && P[j] <= P[dq.back()]) dq.pop_back();
18	dq.push_back(j);
19	}
20	return ans <= n ? ans : -1;
21	}
22
23	int main() {
24	vector<int> a = {2, -1, 2};
25	long long K = 3;
26	cout << shortestSubarrayAtLeastK(a, K) << '\n';
27	return 0;
28	}
29

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	int longestSubarrayWithinLimit(const vector<int>& a, int limit) {
5	int n = (int)a.size();
6	deque<int> dqMax; // decreasing by value
7	deque<int> dqMin; // increasing by value
8	int L = 0, ans = 0;
9	for (int R = 0; R < n; ++R) {
10	// Insert a[R] into both deques with proper monotonicity
11	while (!dqMax.empty() && a[dqMax.back()] <= a[R]) dqMax.pop_back();
12	dqMax.push_back(R);
13	while (!dqMin.empty() && a[dqMin.back()] >= a[R]) dqMin.pop_back();
14	dqMin.push_back(R);
15	// Shrink from the left until the constraint is satisfied
16	while (!dqMax.empty() && !dqMin.empty() && a[dqMax.front()] - a[dqMin.front()] > limit) {
17	if (dqMax.front() == L) dqMax.pop_front();
18	if (dqMin.front() == L) dqMin.pop_front();
19	++L;
20	}
21	ans = max(ans, R - L + 1);
22	}
23	return ans;
24	}
25
26	int main() {
27	vector<int> a = {8, 2, 4, 7};
28	int limit = 4;
29	cout << longestSubarrayWithinLimit(a, limit) << '\n'; // Expected 2
30	return 0;
31	}
32