Stacks & Queues

Monotonic Queue & Deque

Monotonic Queue (and Deque)

A comprehensive guide for competitive programming and interviews.

Table of Contents

  1. What is a Deque?
  2. Deque vs Vector vs List
  3. What is a Monotonic Queue?
  4. The Key Problem: Sliding Window Maximum/Minimum
  5. Why Each Element is Processed O(1) Amortized
  6. Sliding Window Minimum
  7. Advanced Applications
  8. Monotonic Queue vs Monotonic Stack — When to Use Which
  9. Implementation Tips

What is a Deque?

A deque (double-ended queue, pronounced "deck") is a data structure that supports insertion and removal at both ends in O(1) time. It combines the strengths of a stack (LIFO) and a queue (FIFO) into one structure.

front ... ... ... back push_front pop_front push_back pop_back All four operations are O(1).

C++ std::deque<T> Interface

CPP
#include <deque>
deque<int> dq;

// Add elements
dq.push_back(10);    // Add to back:  [..., 10]
dq.push_front(5);    // Add to front: [5, ..., 10]

// Remove elements
dq.pop_back();       // Remove from back
dq.pop_front();      // Remove from front

// Access elements
dq.front();          // Peek at front element
dq.back();           // Peek at back element
dq[i];               // Random access (O(1))

// Query
dq.size();           // Number of elements
dq.empty();          // Is it empty?

Internal Implementation of std::deque

Unlike std::vector (one contiguous block) or std::list (linked list of nodes), std::deque uses a sequence of fixed-size arrays (called "blocks" or "chunks"), managed through a central "map" (an array of pointers to blocks).

Map (array of block pointers): * * * * * A B C B C D C D E Fixed-size arrays (blocks) empty block 1 block 2 block 3 empty - push_front: fill empty slots in leftmost block (or allocate new block) - push_back: fill empty slots in rightmost block (or allocate new block) - Random access: compute which block + offset within block O(1)

This design gives O(1) amortized push/pop at both ends AND O(1) random access, at the cost of slightly worse cache performance than vector (elements are not in one contiguous block).

Key property: Unlike vector, deque does NOT invalidate references/iterators to elements not at the front/back when you push to either end (because existing blocks are not moved).

Deque vs Vector vs List

Operation vector deque list push_back O(1)* O(1)* O(1) push_front O(n) O(1)* O(1) pop_back O(1) O(1) O(1) pop_front O(n) O(1) O(1) Random access O(1) O(1) O(n) Insert middle O(n) O(n) O(1)** Memory overhead Low Medium High Cache perf Best Good Poor Contiguous mem Yes No No Best for General purpose array Both-end ops + random access Frequent middle insert/delete * amortized ** O(1) with iterator, O(n) to find the position

When to use deque over vector:

  • You need O(1) push/pop at the front (sliding window problems!)
  • You need a queue that also supports random access

When to stick with vector:

  • You don't need front operations
  • Cache performance matters (tight inner loops)
  • You want guaranteed contiguous memory

What is a Monotonic Queue?

A monotonic queue is a deque where the elements are maintained in monotonically increasing (or decreasing) order. Unlike a monotonic stack (which only removes from one end), a monotonic queue removes from both ends:

  • Back removal: When a new element is added, pop all elements from the back that violate the monotonic property (same as monotonic stack).
  • Front removal: When an element "expires" (leaves the sliding window), pop it from the front.

This dual-removal capability is what makes it perfect for sliding window problems.

Monotonic Decreasing Queue (for sliding window maximum):

  Front ────────────────────── Back
  [largest, ..., ..., smallest]
   ↑                           ↑
   This is the window max.     New elements enter here
   Expired elements leave      (after popping smaller ones).
   from here.

  Invariants:
  1. Values are in decreasing order from front to back.
  2. All indices in the deque are within the current window.
  3. The front is always the maximum of the current window.

Why is the Front Always the Window Maximum?

Because we maintain decreasing order: the front is the largest element. And we ensure the front is always within the window by popping expired elements. So the front is always the largest element within the current window.

Why Pop Smaller Elements from the Back?

When a new element x enters the window, any element y in the deque where y <= x can never be the window maximum in the future. Why?

  1. x is newer than y, so x will stay in the window at least as long as y.
  2. x >= y, so as long as both are in the window, x beats y.
  3. Therefore, y is completely dominated and can be discarded.
Before adding x=5:
  deque = [7, 4, 3, 1]   (window contains these values)
                   ↑ ↑
                   These are smaller than 5
                   and entered the window BEFORE 5.
                   They'll expire BEFORE 5.
                   So 5 will always be >= them.
                   They can NEVER be the max while 5 exists.

After adding x=5:
  Pop 1 (1 < 5), pop 3 (3 < 5), pop 4 (4 < 5).
  deque = [7, 5]

  7 stays because 7 > 5 (7 could still be the max while 7 is in the window).

The Key Problem: Sliding Window Maximum

Problem Statement (LeetCode 239)

Given an array nums and a window size k, return the maximum value in each window of size k as the window slides from left to right.

Input:  nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]

Windows:
  [1, 3, -1]  → max = 3
  [3, -1, -3] → max = 3
  [-1, -3, 5] → max = 5
  [-3, 5, 3]  → max = 5
  [5, 3, 6]   → max = 6
  [3, 6, 7]   → max = 7

Approach 1: Brute Force O(nk)

For each window position, scan all k elements to find the maximum.

CPP
// Brute force — O(nk)
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    for (int i = 0; i <= n - k; i++) {
        int maxVal = nums[i];
        for (int j = i; j < i + k; j++) {
            maxVal = max(maxVal, nums[j]);
        }
        result.push_back(maxVal);
    }
    return result;
}

For n = 10^5 and k = 10^4, this is 10^9 operations — too slow.

Approach 2: Monotonic Queue O(n)

CPP
#include <bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // stores INDICES in decreasing order of their values
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // Step 1: Remove expired elements from the front.
        // An element is expired if its index is outside the window [i-k+1, i].
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Step 2: Remove elements from the back that are smaller than nums[i].
        // They can never be the maximum while nums[i] is in the window.
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        // Step 3: Add current element's index to the back.
        dq.push_back(i);

        // Step 4: Record the answer once the first window is fully formed.
        // The first full window ends at index k-1.
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]); // front = index of max in window
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int x : res) cout << x << " ";
    // Output: 3 3 5 5 6 7
}

Detailed Visual Walkthrough

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

We store INDICES in the deque. I'll show (index:value) for clarity.

════════════════════════════════════════════════════════════════════════
i=0, nums[0]=1
  Expire: nothing (deque empty)
  Back cleanup: nothing
  Push: 0
  Deque: [(0:1)]
  Window not yet full (need i >= 2).

════════════════════════════════════════════════════════════════════════
i=1, nums[1]=3
  Expire: nothing
  Back cleanup: nums[0]=1 <= nums[1]=3 → pop (0:1)
  Push: 1
  Deque: [(1:3)]
  Window not yet full.

  Why pop (0:1)?  As long as index 1 (value 3) is in the window,
  index 0 (value 1) can never be the max. And index 1 will outlast
  index 0 in every future window.

════════════════════════════════════════════════════════════════════════
i=2, nums[2]=-1
  Expire: nothing (front index 1 > 2-3=-1, so still valid)
  Back cleanup: nums[1]=3 > nums[2]=-1 → don't pop
  Push: 2
  Deque: [(1:3), (2:-1)]
  Window [1,3,-1] is full. Max = nums[dq.front()] = nums[1] = 3.
  result = [3]

  Deque visualization:
      front                    back
      ┌────────┬────────┐
      │ (1:3)  │ (2:-1) │
      └────────┴────────┘
        ↑ max

════════════════════════════════════════════════════════════════════════
i=3, nums[3]=-3
  Expire: front index 1 > 3-3=0 → valid, don't remove
  Back cleanup: nums[2]=-1 > nums[3]=-3 → don't pop
  Push: 3
  Deque: [(1:3), (2:-1), (3:-3)]
  Window [3,-1,-3]. Max = nums[1] = 3.
  result = [3, 3]

  Deque visualization:
      front                              back
      ┌────────┬────────┬─────────┐
      │ (1:3)  │ (2:-1) │ (3:-3)  │
      └────────┴────────┴─────────┘
        ↑ max
        Note: index 1 is still in window [1,2,3]

════════════════════════════════════════════════════════════════════════
i=4, nums[4]=5
  Expire: front index 1 <= 4-3=1 → EXPIRED! Pop front.
  Deque: [(2:-1), (3:-3)]

  Back cleanup: nums[3]=-3 <= 5 → pop. nums[2]=-1 <= 5 → pop.
  Deque: []
  Push: 4
  Deque: [(4:5)]
  Window [-1,-3,5]. Max = nums[4] = 5.
  result = [3, 3, 5]

  What happened: 5 is so large it wiped out everything.
  And index 1 expired (it's outside window [2,3,4]).

════════════════════════════════════════════════════════════════════════
i=5, nums[5]=3
  Expire: front index 4 > 5-3=2 → valid
  Back cleanup: nums[4]=5 > 3 → don't pop
  Push: 5
  Deque: [(4:5), (5:3)]
  Window [-3,5,3]. Max = nums[4] = 5.
  result = [3, 3, 5, 5]

════════════════════════════════════════════════════════════════════════
i=6, nums[6]=6
  Expire: front index 4 > 6-3=3 → valid
  Back cleanup: nums[5]=3 <= 6 → pop. nums[4]=5 <= 6 → pop.
  Deque: []
  Push: 6
  Deque: [(6:6)]
  Window [5,3,6]. Max = nums[6] = 6.
  result = [3, 3, 5, 5, 6]

════════════════════════════════════════════════════════════════════════
i=7, nums[7]=7
  Expire: front index 6 > 7-3=4 → valid
  Back cleanup: nums[6]=6 <= 7 → pop.
  Deque: []
  Push: 7
  Deque: [(7:7)]
  Window [3,6,7]. Max = nums[7] = 7.
  result = [3, 3, 5, 5, 6, 7]

════════════════════════════════════════════════════════════════════════
FINAL RESULT: [3, 3, 5, 5, 6, 7]

Why Each Element is Processed O(1) Amortized

This is the crucial complexity argument:

For each element nums[i], exactly one push_back happens.           → n total pushes

Each element is removed at most once, either via:
  - pop_front (expired)          → at most n total front pops
  - pop_back  (dominated)        → at most n total back pops

Total operations: at most 3n = O(n).

Amortized cost per element: O(1).

Even though a single element (like 5 in our example) might cause multiple back pops in one step, the total number of back pops across ALL steps is bounded by n (each element can only be popped once).

This is the same amortized argument as for the monotonic stack, extended to handle front removals.

Sliding Window Minimum

The sliding window minimum is the mirror image: maintain an increasing deque (smallest at front) instead of a decreasing one.

CPP
#include <bits/stdc++.h>
using namespace std;

vector<int> minSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // stores indices in INCREASING order of their values
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // Remove expired elements from front
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Remove elements from back that are LARGER than nums[i]
        // (they can never be the minimum while nums[i] is in the window)
        while (!dq.empty() && nums[dq.back()] >= nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]); // front = index of min in window
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = minSlidingWindow(nums, k);
    for (int x : res) cout << x << " ";
    // Output: -1 -3 -3 -3 3 3
}

Verification:

Windows:
  [1, 3, -1]  → min = -1
  [3, -1, -3] → min = -3
  [-1, -3, 5] → min = -3
  [-3, 5, 3]  → min = -3
  [5, 3, 6]   → min = 3
  [3, 6, 7]   → min = 3

Summary of Max vs Min

Sliding Window MAX Sliding Window MIN Deque order Decreasing (front=max) Increasing (front=min) Back pop cond. nums[back] <= nums[i] nums[back] >= nums[i] Answer nums[dq.front()] nums[dq.front()]

Advanced Applications

Problem 1: Shortest Subarray with Sum at Least K (LeetCode 862)

Problem: Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If no such subarray exists, return -1.

Critical detail: The array can contain negative numbers. This makes the problem much harder than the classic sliding window (which only works for non-negative values).

Input: nums = [2, -1, 2], k = 3
Output: 3  (the entire array sums to 3)

Input: nums = [84, -37, 32, 40, 95], k = 167
Output: 3  (subarray [32, 40, 95] has sum 167)

Key Insight: Prefix Sums + Monotonic Deque

Let prefix[i] = nums[0] + nums[1] + ... + nums[i-1] (with prefix[0] = 0).

The sum of subarray nums[j..i-1] = prefix[i] - prefix[j].

We want to find the shortest subarray with sum >= k, i.e., minimize i - j such that prefix[i] - prefix[j] >= k, or equivalently prefix[j] <= prefix[i] - k.

For each i, we want the largest j < i such that prefix[j] <= prefix[i] - k.

Why a monotonic deque?

We maintain a deque of indices with increasing prefix sums. Two key observations:

  1. Front removal (finding the answer): For the current i, check if prefix[dq.front()] <= prefix[i] - k. If so, this j gives a valid subarray, and we can pop it from the front (no future i' will produce a shorter subarray with this j, since i' > i means i' - j > i - j).

  2. Back removal (maintaining monotonicity): If prefix[dq.back()] >= prefix[i], we can discard dq.back(). Why? For any future query looking for prefix[j] <= threshold, index i is strictly better than dq.back(): it has a smaller (or equal) prefix sum AND a larger index (so it gives a shorter subarray).

prefix: [0, 2, 1, 3]   (for nums = [2, -1, 2])

i=0: prefix[0]=0. Deque: [0]
i=1: prefix[1]=2.
     Front check: prefix[0]=0 <= 2-3=-1? No.
     Back check:  prefix[0]=0 <= 2? Yes, keep. Push 1.
     Deque: [0, 1]
i=2: prefix[2]=1.
     Front check: prefix[0]=0 <= 1-3=-2? No.
     Back check:  prefix[1]=2 >= prefix[2]=1 → pop 1.
     Push 2. Deque: [0, 2]
i=3: prefix[3]=3.
     Front check: prefix[0]=0 <= 3-3=0? Yes! len = 3-0 = 3. Pop front.
     Deque: [2]
     Front check: prefix[2]=1 <= 0? No. Stop.
     Back check:  prefix[2]=1 <= 3? Keep. Push 3.
     Deque: [2, 3]

Answer: 3

Complete C++ Solution:

CPP
#include <bits/stdc++.h>
using namespace std;

int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    // Compute prefix sums (use long long to avoid overflow)
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    deque<int> dq; // stores indices into prefix[], increasing prefix values
    int ans = INT_MAX;

    for (int i = 0; i <= n; i++) {
        // Step 1: Check front — can we form a valid subarray?
        // prefix[i] - prefix[dq.front()] >= k means subarray [dq.front(), i-1] works.
        while (!dq.empty() && prefix[i] - prefix[dq.front()] >= k) {
            ans = min(ans, i - dq.front());
            dq.pop_front(); // This j is consumed — no future i gives shorter subarray
        }

        // Step 2: Maintain increasing monotonicity of prefix sums
        // If prefix[dq.back()] >= prefix[i], dq.back() is dominated by i:
        //   - prefix[i] <= prefix[dq.back()] (so i satisfies more queries)
        //   - i > dq.back() (so i gives shorter subarrays for future queries)
        while (!dq.empty() && prefix[dq.back()] >= prefix[i]) {
            dq.pop_back();
        }

        dq.push_back(i);
    }

    return ans == INT_MAX ? -1 : ans;
}

int main() {
    vector<int> nums1 = {2, -1, 2};
    cout << shortestSubarray(nums1, 3) << "\n"; // Output: 3

    vector<int> nums2 = {84, -37, 32, 40, 95};
    cout << shortestSubarray(nums2, 167) << "\n"; // Output: 3
}

Why this is tricky and why we can't use a simple sliding window:

With negative numbers, growing the window can decrease the sum, and shrinking it can increase the sum. The standard two-pointer approach breaks because it relies on the invariant that extending the window never decreases the sum. The prefix sum + monotonic deque approach elegantly handles this.

Complexity: Time O(n), Space O(n).

Problem 2: Jump Game VI (LeetCode 1696)

Problem: Given a 0-indexed integer array nums and an integer k, you start at index 0. In one step, you can jump from index i to any index j such that i < j <= min(i + k, n - 1). Return the maximum score you can get when reaching the last index, where the score is the sum of nums[j] for all visited indices.

Input: nums = [1, -1, -2, 4, -7, 3], k = 2
Output: 7
Explanation: Jump 0 → 1 → 3 → 5 for score 1 + (-1) + 4 + 3 = 7.

Key Insight: DP + Monotonic Queue

Define dp[i] = maximum score to reach index i.

Recurrence: dp[i] = nums[i] + max(dp[j] for j in [i-k, i-1])

Base case: dp[0] = nums[0].

The recurrence says: to reach index i, we add nums[i] to the best score among the previous k positions. This is exactly a sliding window maximum over the dp array with window size k!

dp values being computed left to right:

  dp:    [dp[0], dp[1], dp[2], ..., dp[i-1]]
                         ←── window of size k ──→
                                              dp[i] = nums[i] + max of this window

Without the monotonic deque, we'd need O(k) per index to find the max → O(nk) total. With the deque, we get O(1) amortized per index → O(n) total.

Complete C++ Solution:

CPP
#include <bits/stdc++.h>
using namespace std;

int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];

    deque<int> dq; // stores indices, decreasing dp values (window max at front)
    dq.push_back(0);

    for (int i = 1; i < n; i++) {
        // Remove expired elements (outside the window [i-k, i-1])
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }

        // dp[i] = nums[i] + max dp value in window
        dp[i] = nums[i] + dp[dq.front()];

        // Maintain decreasing deque for dp values
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    return dp[n - 1];
}

int main() {
    vector<int> nums = {1, -1, -2, 4, -7, 3};
    cout << maxResult(nums, 2) << "\n"; // Output: 7
}

Trace:

nums = [1, -1, -2, 4, -7, 3], k = 2

i=0: dp[0] = 1.         Deque: [0]   (dp vals: [1])
i=1: No expiry.
     dp[1] = -1 + dp[0] = -1 + 1 = 0.
     dp[0]=1 > dp[1]=0, keep 0.
     Deque: [0, 1]       (dp vals: [1, 0])
i=2: No expiry (front=0, 0 >= 2-2=0 → valid).
     dp[2] = -2 + dp[0] = -2 + 1 = -1.
     dp[1]=0 > dp[2]=-1, keep 1.
     Deque: [0, 1, 2]    (dp vals: [1, 0, -1])
i=3: Expire: front=0, 0 < 3-2=1 → pop!
     Deque: [1, 2]       (dp vals: [0, -1])
     dp[3] = 4 + dp[1] = 4 + 0 = 4.
     dp[2]=-1 <= 4 → pop. dp[1]=0 <= 4 → pop.
     Deque: [3]           (dp vals: [4])
i=4: No expiry (3 >= 4-2=2).
     dp[4] = -7 + dp[3] = -7 + 4 = -3.
     dp[3]=4 > dp[4]=-3, keep 3.
     Deque: [3, 4]        (dp vals: [4, -3])
i=5: Expire: front=3, 3 >= 5-2=3 → valid.
     dp[5] = 3 + dp[3] = 3 + 4 = 7.
     dp[4]=-3 <= 7 → pop. dp[3]=4 <= 7 → pop.
     Deque: [5]

Answer: dp[5] = 7.

Complexity: Time O(n), Space O(n).

General Pattern: Whenever you have a DP recurrence of the form dp[i] = f(i) + max/min(dp[j] for j in [i-k, i-1]), you can optimize from O(nk) to O(n) using a monotonic deque.

Problem 3: Constrained Subsequence Sum (LeetCode 1425)

Problem: Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence such that for every two consecutive elements nums[i] and nums[j] in the subsequence, j - i <= k. (We must include at least one element.)

Input: nums = [10, 2, -10, 5, 20], k = 2
Output: 37
Explanation: Subsequence [10, 2, 5, 20] — consecutive indices differ by at most 2.

Key Insight: This is structurally identical to Jump Game VI!

Define dp[i] = maximum sum of a valid subsequence ending at index i.

Recurrence: dp[i] = nums[i] + max(0, max(dp[j] for j in [i-k, i-1]))

The max(0, ...) accounts for the option of starting a new subsequence at index i (if all previous dp values are negative, we're better off starting fresh).

The answer is max(dp[i] for all i).

Complete C++ Solution:

CPP
#include <bits/stdc++.h>
using namespace std;

int constrainedSubsetSum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    deque<int> dq; // stores indices, decreasing dp values
    int ans = INT_MIN;

    for (int i = 0; i < n; i++) {
        // Remove expired elements
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }

        // dp[i] = nums[i] + max(0, best dp in window)
        dp[i] = nums[i];
        if (!dq.empty() && dp[dq.front()] > 0) {
            dp[i] += dp[dq.front()];
        }

        // Maintain decreasing deque
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        ans = max(ans, dp[i]);
    }

    return ans;
}

int main() {
    vector<int> nums = {10, 2, -10, 5, 20};
    cout << constrainedSubsetSum(nums, 2) << "\n"; // Output: 37
}

Trace:

nums = [10, 2, -10, 5, 20], k = 2

i=0: dp[0] = 10.        Deque: [0]. ans = 10.
i=1: dp[1] = 2 + 10 = 12.
     Pop 0 (dp[0]=10 <= 12).
     Deque: [1]. ans = 12.
i=2: dp[2] = -10 + 12 = 2.
     Deque: [1, 2]. ans = 12.
i=3: Expire: 1 >= 3-2=1 → valid.
     dp[3] = 5 + 12 = 17.
     Pop 2 (2 <= 17), pop 1 (12 <= 17).
     Deque: [3]. ans = 17.
i=4: dp[4] = 20 + 17 = 37.
     Pop 3 (17 <= 37).
     Deque: [4]. ans = 37.

Answer: 37.

Complexity: Time O(n), Space O(n).

Problem 4: Max Value of Equation (LeetCode 1499) — Bonus

Problem: Given an array of points [xi, yi] sorted by xi, find the maximum value of yi + yj + |xi - xj| where |xi - xj| <= k and i < j.

Since points are sorted by xi and i < j, we have xj >= xi, so |xi - xj| = xj - xi.

Therefore: yi + yj + xj - xi = (yj + xj) + (yi - xi).

For each j, we want to maximize (yi - xi) over all valid i (where xj - xi <= k). This is a sliding window maximum over the value yi - xi with the constraint that xi >= xj - k.

CPP
#include <bits/stdc++.h>
using namespace std;

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    deque<pair<int, int>> dq; // (yi - xi, xi) — decreasing by yi - xi
    int ans = INT_MIN;

    for (auto& p : points) {
        int xj = p[0], yj = p[1];

        // Remove expired points: xi < xj - k
        while (!dq.empty() && dq.front().second < xj - k) {
            dq.pop_front();
        }

        // If deque non-empty, try to update answer
        if (!dq.empty()) {
            ans = max(ans, yj + xj + dq.front().first); // (yj + xj) + max(yi - xi)
        }

        // Maintain decreasing deque on (yi - xi)
        int val = yj - xj;
        while (!dq.empty() && dq.back().first <= val) {
            dq.pop_back();
        }
        dq.push_back({val, xj});
    }

    return ans;
}

Complexity: Time O(n), Space O(n).

Monotonic Queue vs Monotonic Stack — When to Use Which

MONOTONIC STACK MONOTONIC QUEUE Data structure: stack (one open end) Data structure: deque (two open ends) Removal: only from top - Top: when invariant violated by new element Removal: from front AND back - Back: when invariant violated by new element (same as stack) - Front: when element expires (leaves the window) No window constraint Fixed-size or bounded window Answers "nearest" queries: - Next greater/smaller - Previous greater/smaller Answers "range" queries: - Window max/min - Best value in last k elements Typical problems: - Next greater element - Largest rect histogram - Daily temperatures - Stock span - Trapping rain water Typical problems: - Sliding window max/min - DP optimization (window max) - Shortest subarray with sum >= k - Jump game / constrained subseq - Max value of equation Key question: "What is the nearest element with property X?" Key question: "What is the max/min in a sliding window of size k?"

Decision Flowchart

Do you need max/min or nearest element info? "Nearest" greater or smaller "Range/Window" max or min over k MONOTONIC STACK MONOTONIC QUEUE (DEQUE)

The Overlap

Both maintain monotonic order by popping from one end. The deque adds front-popping for window expiration. In fact, a monotonic stack is a special case of a monotonic queue where the window is infinite (nothing ever expires from the front).

Implementation Tips

1. Always Store INDICES, Not Values

CPP
// GOOD — store indices
deque<int> dq;
dq.push_back(i);
// Access value: nums[dq.front()], nums[dq.back()]
// Check expiry: dq.front() <= i - k

// BAD — store values
deque<int> dq;
dq.push_back(nums[i]);
// Can't check if front has expired!
// Can't compute distances!

Storing indices gives you:

  • Expiration checking: Compare dq.front() to the window boundary.
  • Distance computation: i - dq.front() gives the subarray length.
  • Value access: nums[dq.front()] or dp[dq.front()] retrieves the value.

2. The Order of Operations Matters

For sliding window max/min, the standard order is:

CPP
for (int i = 0; i < n; i++) {
    // 1. Remove expired from front
    // 2. Remove dominated from back
    // 3. Push current
    // 4. Record answer (if window is full)
}

For DP optimization, you might need to record the answer BEFORE pushing:

CPP
for (int i = 0; i < n; i++) {
    // 1. Remove expired from front
    // 2. Use dq.front() to compute dp[i]     ← answer comes from deque state BEFORE push
    // 3. Remove dominated from back
    // 4. Push current
}

3. Handling Ties (Equal Elements)

For sliding window maximum with <=:

CPP
while (!dq.empty() && nums[dq.back()] <= nums[i])  // Pop equal elements too

This is correct because if nums[dq.back()] == nums[i], the element at index i is newer and will stay in the window longer, so it dominates.

For problems where you need to keep duplicates (rare), use strict <:

CPP
while (!dq.empty() && nums[dq.back()] < nums[i])   // Keep equal elements

4. The "Virtual Sentinel" Trick

For problems like Largest Rectangle in Histogram, adding a virtual element (height 0) at the end forces everything to be popped:

CPP
for (int i = 0; i <= n; i++) {  // Note: i goes to n (one past the array)
    int h = (i == n) ? 0 : heights[i];
    // ...
}

The equivalent for monotonic queues is less common, but you can add sentinel values to avoid special-casing the first or last window.

5. Space Optimization

The deque never holds more than k elements (where k is the window size), so the space is actually O(min(n, k)). In practice, this rarely matters since k <= n.

6. Template for DP + Monotonic Deque Optimization

Whenever you have a DP of the form:

dp[i] = f(i) + max(dp[j] for j in [i-k, i-1])

The optimization template is:

CPP
deque<int> dq;
for (int i = 0; i < n; i++) {
    // Expire
    while (!dq.empty() && dq.front() < i - k) dq.pop_front();

    // Compute dp[i] using front of deque
    dp[i] = f(i) + (dq.empty() ? BASE_CASE : dp[dq.front()]);

    // Maintain monotonicity
    while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
    dq.push_back(i);
}

Summary Cheat Sheet

MONOTONIC QUEUE CHEAT SHEET Structure: deque<int> storing INDICES For Sliding Window MAX (decreasing deque): - Front = index of maximum in current window - Pop front if: dq.front() <= i - k (expired) - Pop back if: nums[dq.back()] <= nums[i] (dominated) For Sliding Window MIN (increasing deque): - Front = index of minimum in current window - Pop front if: dq.front() <= i - k (expired) - Pop back if: nums[dq.back()] >= nums[i] (dominated) Time: O(n) -- each element pushed once, popped at most once Space: O(k) -- deque holds at most k elements DP Optimization Pattern: dp[i] = f(i) + max/min(dp[j] for j in [i-k, i-1]) Use monotonic deque to find max/min in O(1) amortized Reduces O(nk) DP to O(n) Key Advantages over Other Approaches: vs Brute Force: O(n) vs O(nk) vs Segment Tree: O(n) vs O(n log n) vs Multiset: O(n) vs O(n log k) vs Sparse Table: dynamic windows
All DSA Notes