Monotonic Queue & Deque DP Optimization: Amortized Linear Time for Sliding Windows

1. The Sliding Window Dynamic Programming Bottleneck

Consider a state transition where an agent at index i can transition from any preceding state within a bounded window [i - K, i - 1]:

If N = 10^5 and K = 5 × 10^4, iterating over all K candidates requires 5 × 10^9 operations, causing severe Time Limit Exceeded (TLE) failures. Balanced binary search trees (e.g., std::multiset) achieve O(N log K), but node rebalancing and heap allocations introduce substantial latency penalties.

2. The Monotonic Deque Invariant: Eliminating Dominated Candidates

Let index j_1 < j_2. If dp[j_1] ≥ dp[j_2], then state j_1 is strictly dominated by j_2:

• j_2 has an equal or smaller cost (dp[j_2] ≤ dp[j_1]).
• j_2 is newer than j_1, meaning it will survive inside the sliding window [i - K, i] strictly longer into future iterations.

Because j_1 can never serve as an optimal predecessor for any future index, it can be permanently discarded! By purging dominated elements from the back of a double-ended queue, the queue elements remain strictly monotonically increasing from front to back.

3. C++ Implementation: Jump Game VI (LeetCode 1696)

int maxResult(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    deque<int> dq; // Stores indices with monotonically decreasing dp values
    dq.push_back(0);

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

        // 2. Front of deque is optimal predecessor
        dp[i] = nums[i] + dp[dq.front()];

        // 3. Maintain monotonic decreasing invariant: pop smaller back elements
        while (!dq.empty() && dp[dq.back()] ≤ dp[i]) {
            dq.pop_back();
        }

        // 4. Push current index
        dq.push_back(i);
    }

    return dp[n - 1];
}

4. Amortized Complexity Analysis & Proof

While an individual iteration i may trigger multiple pop_back() calls, each index 0 ≤ i < N is pushed onto the deque exactly once. An element popped from the back or front is never re-inserted.

This guarantees that the aggregate execution time across the entire sequence is bounded by 2N operations, achieving true O(1) amortized time per transition.

5. Monotonic Queue vs. Monotonic Stack: Architectural Disambiguation

Software engineers frequently confuse Monotonic Queues and Monotonic Stacks due to their shared monotonic ordering invariant. Their operational purposes are strictly distinct:

• Monotonic Queue (Sliding Window Expiration): Operates as a double-ended queue (deque). Elements expire from the front when they age out of an active temporal window [i - K, i], while dominated elements are popped from the back. Used for sliding window maximum/minimum and DP window transitions.
• Monotonic Stack (Unbounded Historical Search): Operates as a single-ended stack (LIFO). Elements have no temporal lifespan expiration; elements are popped exclusively from the top when a newer element breaks monotonicity. Used for Next Greater Element, Daily Temperatures, and Largest Rectangle in Histogram.

6. 2D Sliding Window DP & Separable Image Filters

In multidimensional dynamic programming and computer vision (e.g., morphological erosion and dilation), we frequently require computing the minimum value inside a 2D bounding box R × C across an N × M grid.

Because the min() operator is strictly separable: min_{x, y} A[x][y] = min_x (min_y A[x][y]), the 2D window problem decouples into two consecutive 1D monotonic deque passes:

1. Horizontal Sweep: Run a 1D monotonic queue across each row of the grid with window width C, producing an intermediate grid in O(NM) time.
2. Vertical Sweep: Run a 1D monotonic queue down each column of the intermediate grid with window height R, computing the final 2D window minimums in O(NM) time.

This dimensional separation reduces naive O(NM × RC) filtering to optimal O(NM) linear time independent of kernel dimensions.

7. High-Performance Circular Ring Buffer Implementation

While std::deque in C++ provides asymptotic O(1) operations, its internal chunked page-map design causes heap pointer chasing and memory fragmentation. In competitive programming and real-time gaming engines, a fixed-size circular array delivers 3x–5x faster throughput:

Using a flat array completely avoids dynamic memory allocation, keeping the active sliding window cache lines resident in hardware L1 data caches.

8. Algorithmic Comparison: Window Optimization Strategies