Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

4 / 4

Time Complexity Optimization

From O(nk) to O(n) — Understanding the Speedup

We've developed the monotonic deque algorithm and proven its correctness. Now comes the crucial question: Why is it O(n) and not something worse?

At first glance, the algorithm looks suspicious. We have nested loops—a while loop inside a for loop. Doesn't that suggest O(n²) or O(nk) complexity?

The answer lies in amortized analysis—a powerful technique for analyzing algorithms where individual operations may vary in cost, but the total cost across all operations is bounded. Understanding amortized analysis is essential for algorithm design, as it reveals the true efficiency of data structures like dynamic arrays, splay trees, and our monotonic deque.

What You Will Learn

By the end of this page, you will understand why the monotonic deque achieves O(n) time complexity, how to apply amortized analysis to prove this bound, how it compares to alternative approaches (O(nk) naive, O(n log k) heap), and practical performance considerations for real-world systems.

The Amortized Analysis Framework

What is Amortized Analysis?

Amortized analysis is a method of analyzing the average performance of each operation in a sequence, where the sequence as a whole matters more than individual operations. Unlike average-case analysis (which assumes a probability distribution), amortized analysis guarantees worst-case bounds over any sequence of operations.

Three Common Techniques:

Aggregate Analysis — Compute total cost of n operations, divide by n
Accounting Method — Assign costs to operations; overcharge some to pay for others
Potential Method — Define a potential function; actual cost + change in potential = amortized cost

For the monotonic deque, aggregate analysis provides the clearest proof.

The Key Insight

The insight is that even though a single iteration might do O(k) work (when many elements are popped), this expensive case can only happen if many cheap cases came before (when elements were pushed without popping). The total work across ALL iterations is bounded by the total number of pushes — which is exactly n.

Proving O(n) with Aggregate Analysis

Let's prove rigorously that the monotonic deque algorithm runs in O(n) time.

The Algorithm's Operations:

For each element at index i, we perform:

Pop from back — Remove dominated elements (while loop)
Push to back — Add current index (single operation)
Pop from front — Remove expired elements (while loop)
Read front — Get maximum (single operation)

Counting Total Operations:

Let's count each operation type across ALL n iterations:

Push operations: Exactly n pushes (each element pushed exactly once)

Pop-back operations: At most n pops

Each element can only be popped from the back once (after being pushed)
Since there are n pushes, there are at most n pop-backs

Pop-front operations: At most n pops

Each element can only be popped from the front once (when it expires)
Since there are n pushes, there are at most n pop-fronts

Read operations: Exactly n - k + 1 reads (one per complete window)

Total Count:

Operation	Count	Individual Cost	Total Cost
Push-back	n	O(1)	O(n)
Pop-back	≤ n	O(1)	O(n)
Pop-front	≤ n	O(1)	O(n)
Read-front	n - k + 1	O(1)	O(n)
Total	≤ 4n	O(1)	O(n)

The Key Observation:

Each element participates in at most 4 operations across its lifetime:

One push-back (when first seen)
At most one pop-back (if dominated by a later element)
At most one pop-front (when it expires from the window)
Zero or more reads (doesn't add to element's operations)

Actually, it's at most 3 operations per element (push, and at most one pop from either end).

Since there are n elements and each participates in O(1) operations, total work is O(n).

The Amortized Bound

While a single iteration of the for loop might do O(k) work (when many elements are dominated and popped), the TOTAL work across all iterations is O(n). Dividing by n iterations gives O(1) AMORTIZED cost per iteration. This is the power of amortized analysis!

operation_counting.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Instrumented version to count operations
 * Demonstrates that total ops ≤ 4n regardless of k
 */
function maxSlidingWindowInstrumented(nums: number[], k: number): {
    result: number[];
    stats: {
        pushBackCount: number;
        popBackCount: number;
        popFrontCount: number;
        readFrontCount: number;
        totalOperations: number;
    };
} {
    const n = nums.length;
    const result: number[] = [];
    const deque: number[] = [];
    
    let pushBackCount = 0;
    let popBackCount = 0;
    let popFrontCount = 0;
    let readFrontCount = 0;
    
    for (let i = 0; i < n; i++) {
        // Pop dominated from back
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
            popBackCount++;
        }
        
        // Push to back
        deque.push(i);
        pushBackCount++;
        
        // Pop expired from front
        while (deque[0] < i - k + 1) {
            deque.shift();
            popFrontCount++;
        }
        
        // Read front (if window complete)
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
            readFrontCount++;
        }
    }
    
    return {
        result,
        stats: {
            pushBackCount,
            popBackCount,
            popFrontCount,
            readFrontCount,
            totalOperations: pushBackCount + popBackCount + popFrontCount + readFrontCount
        }
    };
}
 
// Test with different inputs
const testCases = [
    { nums: [1, 3, -1, -3, 5, 3, 6, 7], k: 3 },
    { nums: [9, 8, 7, 6, 5, 4, 3, 2, 1], k: 3 },  // Decreasing
    { nums: [1, 2, 3, 4, 5, 6, 7, 8, 9], k: 3 },  // Increasing
    { nums: [5, 5, 5, 5, 5, 5, 5, 5, 5], k: 3 },  // All same
];
 
for (const { nums, k } of testCases) {
    const { stats } = maxSlidingWindowInstrumented(nums, k);
    console.log(`n=${nums.length}, k=${k}:`);
    console.log(`  Pushes: ${stats.pushBackCount}`);
    console.log(`  Pop-backs: ${stats.popBackCount}`);
    console.log(`  Pop-fronts: ${stats.popFrontCount}`);
    console.log(`  Total: ${stats.totalOperations} (bound: ${4 * nums.length})`);
}
 
// Output shows total operations are always ≤ 4n
// Worst case scenarios:
// - Decreasing: many pop-fronts, few pop-backs
// - Increasing: many pop-backs, few pop-fronts
// But total is always bounded!

The Accounting Method Perspective

For additional insight, let's view the same proof through the accounting method. This perspective helps build intuition for more complex amortized analyses.

The Accounting Method:

We assign an "amortized cost" to each operation, which may differ from its actual cost. The rule is:

Sum of amortized costs ≥ Sum of actual costs

If we can show amortized costs are O(n) total, then actual costs are O(n) total.

Assignment of Credits:

When we push an element, we charge 3 credits:

1 credit for the push operation itself
1 credit "saved" to pay for a future pop-back
1 credit "saved" to pay for a future pop-front

When we pop an element (from either end), we use the credit it saved, so the pop is "free."

When we read the front, it costs 1 credit.

Accounting Analysis:

Operation	Amortized Cost	Actual Cost	Difference Stored
Push	3	1	+2 (saved for pops)
Pop-back	0	1	-1 (uses saved credit)
Pop-front	0	1	-1 (uses saved credit)
Read	1	1	0

Why It Works:

Each element is pushed exactly once → we collect 3 credits per element
Each element is popped at most once from back OR front → we spend 0-2 credits per element
We always have sufficient credits because pops can't exceed pushes

Total Amortized Cost:

n pushes × 3 credits = 3n credits
(n - k + 1) reads × 1 credit ≈ n credits
Total ≈ 4n credits = O(n)

Since amortized cost ≥ actual cost, actual cost is also O(n).

The Prepayment Intuition

Think of it like prepaying for a service. When you add an element, you prepay for any future "removal work" that element might cause. Since you pay upfront per element, and each element only causes bounded future work, the total is O(n).

Comparison with Alternative Approaches

Let's compare the monotonic deque against all major approaches to understand when each is appropriate.

Algorithm Comparison for Sliding Window Maximum
Approach	Time	Space	Pros	Cons
Naive (rescan)	O(nk)	O(1)*	Simple to implement	Too slow for large k
Max-Heap + Lazy Delete	O(n log k)	O(n)	Uses standard heap	Extra space, log factor
Balanced BST (TreeMap)	O(n log k)	O(k)	Handles duplicates well	Complex implementation
Segment Tree	O(n log n)	O(n)	Flexible for many queries	High constant factor
Monotonic Deque	O(n)	O(k)	Optimal time	Specialized technique

*The naive approach uses O(1) auxiliary space but O(n-k+1) output space

When to Use Each:

Algorithm Selection Guide

•Naive O(nk) — Use when k is very small (k ≤ 10) and n is moderate. The simplicity outweighs the inefficiency.
•Max-Heap O(n log k) — Use when you already have a heap implementation and k is large enough that log k matters, but you don't want to implement a deque.
•Balanced BST O(n log k) — Use when you need to handle additional operations like rank queries or range deletions alongside sliding max.
•Segment Tree O(n log n) — Use when you need random access to any window (not just sliding) or multiple different query types.
•Monotonic Deque O(n) — Use for pure sliding window max/min. It's optimal and should be your default choice.

The Log Factor Matters at Scale

For n = 10^7 and k = 10^6: O(nk) = 10^13 operations (hours), O(n log k) = 2×10^8 operations (seconds), O(n) = 10^7 operations (< 1 second). The log factor is 20× worse than optimal, which can mean TLE in competitive programming.

Space Complexity Analysis

Let's analyze the space usage of the monotonic deque approach and understand the tradeoffs.

Deque Size Bound:

The deque stores indices of elements currently in the window. Since:

We only add indices within the current window
We remove indices that fall outside the window
The window has at most k elements

The deque contains at most k indices at any time.

Total Space Analysis:

Component	Space	Notes
Input array	O(n)	Given, not counted
Deque	O(k)	At most k indices
Output array	O(n - k + 1)	Required for output
Misc variables	O(1)	Loop indices, etc.
Auxiliary Total	O(k) + O(n)	O(n) dominated by output

Tighter Bound on Deque Size:

While O(k) is the worst-case bound, the actual deque size depends on the input pattern:

Input Pattern	Typical Deque Size	Example
Strictly increasing	1	[1, 2, 3, 4, 5]
Strictly decreasing	k	[5, 4, 3, 2, 1]
Random	~log k	Statistical expectation
All same value	1	[5, 5, 5, 5, 5]

Why Decreasing is Worst Case:

In a strictly decreasing sequence, no element dominates any earlier element. Every element in the window becomes a candidate, filling the deque to capacity k.

Why Increasing is Best Case:

In a strictly increasing sequence, each new element dominates all previous elements. The deque always contains just the most recent element.

Space-Time Relationship

There's an interesting relationship: when time is cheap (few pops), space is expensive (many elements in deque). When time is expensive (many pops), space is cheap (elements quickly removed). The product of 'current deque size' and 'pops per iteration' tends to be roughly constant.

Practical Performance Considerations

While asymptotic analysis shows O(n) time, practical performance depends on constants, cache behavior, and implementation details.

Performance Optimization Tips

•Use array-based deque — Circular buffers have better cache locality than linked-list deques. Pre-allocate to size k.
•Avoid JavaScript array.shift() — It's O(n). Use a proper circular buffer Deque class for large inputs.
•Consider parallel windows — For real-time systems processing multiple streams, SIMD operations can process multiple windows simultaneously.
•Pre-allocate output — Allocate result array upfront with size n - k + 1 instead of using push().
•Branch prediction — Increasing sequences have predictable branches (always pop), decreasing have unpredictable branches.

optimized_implementation.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Optimized Sliding Window Maximum
 * 
 * Optimizations:
 * 1. Pre-allocated circular buffer deque
 * 2. Pre-allocated output array
 * 3. Avoid array.shift() O(n) operation
 */
function maxSlidingWindowOptimized(nums: number[], k: number): number[] {
    const n = nums.length;
    if (n === 0 || k === 0) return [];
    if (k === 1) return nums.slice();  // Copy is faster than loop
    
    // Pre-allocate output
    const result = new Array<number>(n - k + 1);
    
    // Circular buffer deque (pre-allocated)
    const deque = new Int32Array(k + 1);  // Typed array for performance
    let head = 0;
    let tail = 0;
    
    // Helper functions for circular buffer
    const isEmpty = () => head === tail;
    const front = () => deque[head];
    const back = () => deque[(tail - 1 + deque.length) % deque.length];
    const pushBack = (val: number) => {
        deque[tail] = val;
        tail = (tail + 1) % deque.length;
    };
    const popBack = () => {
        tail = (tail - 1 + deque.length) % deque.length;
    };
    const popFront = () => {
        head = (head + 1) % deque.length;
    };
    
    for (let i = 0; i < n; i++) {
        // Remove dominated from back
        while (!isEmpty() && nums[back()] <= nums[i]) {
            popBack();
        }
        
        // Add current
        pushBack(i);
        
        // Remove expired from front
        const windowStart = i - k + 1;
        while (front() < windowStart) {
            popFront();
        }
        
        // Record result
        if (i >= k - 1) {
            result[i - k + 1] = nums[front()];
        }
    }
    
    return result;
}
 
// Benchmark comparison
function benchmark() {
    const n = 1_000_000;
    const k = 10_000;
    const nums = Array.from({ length: n }, () => Math.floor(Math.random() * 1000));
    
    console.time('Optimized');
    const result1 = maxSlidingWindowOptimized(nums, k);
    console.timeEnd('Optimized');
    
    // Compare with naive array-based deque 
    // (would be much slower due to shift())
}

Real-Time Systems

For real-time systems (stock trading, sensor monitoring), consider using a persistent/immutable deque data structure. This allows multiple threads to share window state safely and enables time-travel debugging by keeping historical window states.

Beyond Sliding Windows: DP Optimization

The monotonic deque technique extends beyond simple sliding window max/min. One of its most powerful applications is optimizing dynamic programming recurrences.

The Pattern:

Many DP problems have recurrences of the form:

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

Naively, this is O(nk). But if cost(j, i) can be decomposed suitably, monotonic deque reduces it to O(n).

Example: Jump Game VI (LeetCode 1696)

Given nums[] and k, start at index 0.
At each position i, you can jump to any position in [i+1, i+k].
Score is sum of nums[] at visited positions.
Find maximum score to reach the end.

Recurrence:

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

The max(dp[j]) over a sliding window is exactly our problem!

jump_game_vi.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * LeetCode 1696: Jump Game VI
 * 
 * DP with monotonic deque optimization
 * Reduces O(nk) to O(n)
 */
function maxResult(nums: number[], k: number): number {
    const n = nums.length;
    const dp = new Array<number>(n);
    dp[0] = nums[0];
    
    // Deque stores indices, values (dp values) are decreasing
    const deque: number[] = [0];
    
    for (let i = 1; i < n; i++) {
        // Remove expired indices from front
        while (deque.length && deque[0] < i - k) {
            deque.shift();
        }
        
        // dp[i] = nums[i] + max(dp[j]) for j in window
        // The front of deque has the max dp[j]
        dp[i] = nums[i] + dp[deque[0]];
        
        // Remove dominated from back (dp values <= dp[i])
        while (deque.length && dp[deque[deque.length - 1]] <= dp[i]) {
            deque.pop();
        }
        
        // Add current index
        deque.push(i);
    }
    
    return dp[n - 1];
}
 
// Example
console.log(maxResult([1, -1, -2, 4, -7, 3], 2));
// Expected: 7 (path: 1 -> -1 -> 4 -> 3 = 7)
 
console.log(maxResult([10, -5, -2, 4, 0, 3], 3));
// Expected: 17 (path: 10 -> 4 -> 3 = 17)
 
console.log(maxResult([1, -5, -20, 4, -1, 3, -6, -3], 2));
// Expected: 0

The Power of Deque-Optimized DP

Many DP problems that appear to require O(n²) or O(nk) can be optimized to O(n) using monotonic deques. The technique applies whenever you need the max/min of the last k DP values. This pattern appears in constrained subsequence problems, jump games, and resource allocation.

Summary: Mastering Monotonic Deque Complexity

We've completed our deep dive into the time complexity of the monotonic deque technique. Let's consolidate everything we've learned:

Key Takeaways

•O(n) Time Proven — Using aggregate analysis: each element is pushed once and popped at most once, giving 3n total operations.
•Amortized Analysis — Individual iterations may cost O(k), but total across all iterations is O(n). Don't be fooled by nested loops!
•Accounting Method — Prepay for future pops when you push. This mental model helps reason about complex amortized algorithms.
•O(k) Space — The deque holds at most k indices. Actual size varies by input pattern but never exceeds k.
•Optimal for Sliding Windows — Beats O(nk) naive by factor of k, beats O(n log k) heap by factor of log k.
•DP Optimization — The technique generalizes to optimize DP recurrences with sliding window maximum/minimum subproblems.

Module Complete: Sliding Window Maximum with Monotonic Deque

You've now mastered one of the most elegant and powerful techniques in competitive programming and algorithm design. The monotonic deque is:

Theoretically optimal — O(n) time, O(k) auxiliary space
Practically efficient — Simple to implement with good cache behavior
Widely applicable — Sliding windows, DP optimization, range queries
Fundamentally important — Teaches amortized analysis, invariant-based design

With this technique in your toolkit, you can tackle a wide range of problems that previously seemed to require O(nk) or O(n log k) complexity. Look for the pattern: whenever you need extremums over sliding ranges, think monotonic deque.

Module Complete

Congratulations! You've completed the Sliding Window Maximum module. You now understand the problem, the deque-based solution, the monotonic deque technique, and its O(n) complexity analysis. Practice on related LeetCode problems to solidify your understanding: 239, 1438, 862, 1696, 1499, 2398.

4 / 4

Loading learning content...

Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

4 / 4

Time Complexity Optimization

From O(nk) to O(n) — Understanding the Speedup

We've developed the monotonic deque algorithm and proven its correctness. Now comes the crucial question: Why is it O(n) and not something worse?

At first glance, the algorithm looks suspicious. We have nested loops—a while loop inside a for loop. Doesn't that suggest O(n²) or O(nk) complexity?

What You Will Learn

The Amortized Analysis Framework

What is Amortized Analysis?

Three Common Techniques:

Aggregate Analysis — Compute total cost of n operations, divide by n
Accounting Method — Assign costs to operations; overcharge some to pay for others
Potential Method — Define a potential function; actual cost + change in potential = amortized cost

For the monotonic deque, aggregate analysis provides the clearest proof.

The Key Insight

Proving O(n) with Aggregate Analysis

Let's prove rigorously that the monotonic deque algorithm runs in O(n) time.

The Algorithm's Operations:

For each element at index i, we perform:

Pop from back — Remove dominated elements (while loop)
Push to back — Add current index (single operation)
Pop from front — Remove expired elements (while loop)
Read front — Get maximum (single operation)

Counting Total Operations:

Let's count each operation type across ALL n iterations:

Push operations: Exactly n pushes (each element pushed exactly once)

Pop-back operations: At most n pops

Each element can only be popped from the back once (after being pushed)
Since there are n pushes, there are at most n pop-backs

Pop-front operations: At most n pops

Each element can only be popped from the front once (when it expires)
Since there are n pushes, there are at most n pop-fronts

Read operations: Exactly n - k + 1 reads (one per complete window)

Total Count:

Operation	Count	Individual Cost	Total Cost
Push-back	n	O(1)	O(n)
Pop-back	≤ n	O(1)	O(n)
Pop-front	≤ n	O(1)	O(n)
Read-front	n - k + 1	O(1)	O(n)
Total	≤ 4n	O(1)	O(n)

The Key Observation:

Each element participates in at most 4 operations across its lifetime:

One push-back (when first seen)
At most one pop-back (if dominated by a later element)
At most one pop-front (when it expires from the window)
Zero or more reads (doesn't add to element's operations)

Actually, it's at most 3 operations per element (push, and at most one pop from either end).

Since there are n elements and each participates in O(1) operations, total work is O(n).

The Amortized Bound

operation_counting.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Instrumented version to count operations
 * Demonstrates that total ops ≤ 4n regardless of k
 */
function maxSlidingWindowInstrumented(nums: number[], k: number): {
    result: number[];
    stats: {
        pushBackCount: number;
        popBackCount: number;
        popFrontCount: number;
        readFrontCount: number;
        totalOperations: number;
    };
} {
    const n = nums.length;
    const result: number[] = [];
    const deque: number[] = [];
    
    let pushBackCount = 0;
    let popBackCount = 0;
    let popFrontCount = 0;
    let readFrontCount = 0;
    
    for (let i = 0; i < n; i++) {
        // Pop dominated from back
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
            popBackCount++;
        }
        
        // Push to back
        deque.push(i);
        pushBackCount++;
        
        // Pop expired from front
        while (deque[0] < i - k + 1) {
            deque.shift();
            popFrontCount++;
        }
        
        // Read front (if window complete)
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
            readFrontCount++;
        }
    }
    
    return {
        result,
        stats: {
            pushBackCount,
            popBackCount,
            popFrontCount,
            readFrontCount,
            totalOperations: pushBackCount + popBackCount + popFrontCount + readFrontCount
        }
    };
}
 
// Test with different inputs
const testCases = [
    { nums: [1, 3, -1, -3, 5, 3, 6, 7], k: 3 },
    { nums: [9, 8, 7, 6, 5, 4, 3, 2, 1], k: 3 },  // Decreasing
    { nums: [1, 2, 3, 4, 5, 6, 7, 8, 9], k: 3 },  // Increasing
    { nums: [5, 5, 5, 5, 5, 5, 5, 5, 5], k: 3 },  // All same
];
 
for (const { nums, k } of testCases) {
    const { stats } = maxSlidingWindowInstrumented(nums, k);
    console.log(`n=${nums.length}, k=${k}:`);
    console.log(`  Pushes: ${stats.pushBackCount}`);
    console.log(`  Pop-backs: ${stats.popBackCount}`);
    console.log(`  Pop-fronts: ${stats.popFrontCount}`);
    console.log(`  Total: ${stats.totalOperations} (bound: ${4 * nums.length})`);
}
 
// Output shows total operations are always ≤ 4n
// Worst case scenarios:
// - Decreasing: many pop-fronts, few pop-backs
// - Increasing: many pop-backs, few pop-fronts
// But total is always bounded!

The Accounting Method Perspective

For additional insight, let's view the same proof through the accounting method. This perspective helps build intuition for more complex amortized analyses.

The Accounting Method:

We assign an "amortized cost" to each operation, which may differ from its actual cost. The rule is:

Sum of amortized costs ≥ Sum of actual costs

If we can show amortized costs are O(n) total, then actual costs are O(n) total.

Assignment of Credits:

When we push an element, we charge 3 credits:

1 credit for the push operation itself
1 credit "saved" to pay for a future pop-back
1 credit "saved" to pay for a future pop-front

When we pop an element (from either end), we use the credit it saved, so the pop is "free."

When we read the front, it costs 1 credit.

Accounting Analysis:

Operation	Amortized Cost	Actual Cost	Difference Stored
Push	3	1	+2 (saved for pops)
Pop-back	0	1	-1 (uses saved credit)
Pop-front	0	1	-1 (uses saved credit)
Read	1	1	0

Why It Works:

Each element is pushed exactly once → we collect 3 credits per element
Each element is popped at most once from back OR front → we spend 0-2 credits per element
We always have sufficient credits because pops can't exceed pushes

Total Amortized Cost:

n pushes × 3 credits = 3n credits
(n - k + 1) reads × 1 credit ≈ n credits
Total ≈ 4n credits = O(n)

Since amortized cost ≥ actual cost, actual cost is also O(n).

The Prepayment Intuition

Comparison with Alternative Approaches

Let's compare the monotonic deque against all major approaches to understand when each is appropriate.

Algorithm Comparison for Sliding Window Maximum
Approach	Time	Space	Pros	Cons
Naive (rescan)	O(nk)	O(1)*	Simple to implement	Too slow for large k
Max-Heap + Lazy Delete	O(n log k)	O(n)	Uses standard heap	Extra space, log factor
Balanced BST (TreeMap)	O(n log k)	O(k)	Handles duplicates well	Complex implementation
Segment Tree	O(n log n)	O(n)	Flexible for many queries	High constant factor
Monotonic Deque	O(n)	O(k)	Optimal time	Specialized technique

*The naive approach uses O(1) auxiliary space but O(n-k+1) output space

When to Use Each:

Algorithm Selection Guide

•Naive O(nk) — Use when k is very small (k ≤ 10) and n is moderate. The simplicity outweighs the inefficiency.
•Max-Heap O(n log k) — Use when you already have a heap implementation and k is large enough that log k matters, but you don't want to implement a deque.
•Balanced BST O(n log k) — Use when you need to handle additional operations like rank queries or range deletions alongside sliding max.
•Segment Tree O(n log n) — Use when you need random access to any window (not just sliding) or multiple different query types.
•Monotonic Deque O(n) — Use for pure sliding window max/min. It's optimal and should be your default choice.

The Log Factor Matters at Scale

Space Complexity Analysis

Let's analyze the space usage of the monotonic deque approach and understand the tradeoffs.

Deque Size Bound:

The deque stores indices of elements currently in the window. Since:

We only add indices within the current window
We remove indices that fall outside the window
The window has at most k elements

The deque contains at most k indices at any time.

Total Space Analysis:

Component	Space	Notes
Input array	O(n)	Given, not counted
Deque	O(k)	At most k indices
Output array	O(n - k + 1)	Required for output
Misc variables	O(1)	Loop indices, etc.
Auxiliary Total	O(k) + O(n)	O(n) dominated by output

Tighter Bound on Deque Size:

While O(k) is the worst-case bound, the actual deque size depends on the input pattern:

Input Pattern	Typical Deque Size	Example
Strictly increasing	1	[1, 2, 3, 4, 5]
Strictly decreasing	k	[5, 4, 3, 2, 1]
Random	~log k	Statistical expectation
All same value	1	[5, 5, 5, 5, 5]

Why Decreasing is Worst Case:

In a strictly decreasing sequence, no element dominates any earlier element. Every element in the window becomes a candidate, filling the deque to capacity k.

Why Increasing is Best Case:

In a strictly increasing sequence, each new element dominates all previous elements. The deque always contains just the most recent element.

Space-Time Relationship

Practical Performance Considerations

While asymptotic analysis shows O(n) time, practical performance depends on constants, cache behavior, and implementation details.

Performance Optimization Tips

•Use array-based deque — Circular buffers have better cache locality than linked-list deques. Pre-allocate to size k.
•Avoid JavaScript array.shift() — It's O(n). Use a proper circular buffer Deque class for large inputs.
•Consider parallel windows — For real-time systems processing multiple streams, SIMD operations can process multiple windows simultaneously.
•Pre-allocate output — Allocate result array upfront with size n - k + 1 instead of using push().
•Branch prediction — Increasing sequences have predictable branches (always pop), decreasing have unpredictable branches.

optimized_implementation.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Optimized Sliding Window Maximum
 * 
 * Optimizations:
 * 1. Pre-allocated circular buffer deque
 * 2. Pre-allocated output array
 * 3. Avoid array.shift() O(n) operation
 */
function maxSlidingWindowOptimized(nums: number[], k: number): number[] {
    const n = nums.length;
    if (n === 0 || k === 0) return [];
    if (k === 1) return nums.slice();  // Copy is faster than loop
    
    // Pre-allocate output
    const result = new Array<number>(n - k + 1);
    
    // Circular buffer deque (pre-allocated)
    const deque = new Int32Array(k + 1);  // Typed array for performance
    let head = 0;
    let tail = 0;
    
    // Helper functions for circular buffer
    const isEmpty = () => head === tail;
    const front = () => deque[head];
    const back = () => deque[(tail - 1 + deque.length) % deque.length];
    const pushBack = (val: number) => {
        deque[tail] = val;
        tail = (tail + 1) % deque.length;
    };
    const popBack = () => {
        tail = (tail - 1 + deque.length) % deque.length;
    };
    const popFront = () => {
        head = (head + 1) % deque.length;
    };
    
    for (let i = 0; i < n; i++) {
        // Remove dominated from back
        while (!isEmpty() && nums[back()] <= nums[i]) {
            popBack();
        }
        
        // Add current
        pushBack(i);
        
        // Remove expired from front
        const windowStart = i - k + 1;
        while (front() < windowStart) {
            popFront();
        }
        
        // Record result
        if (i >= k - 1) {
            result[i - k + 1] = nums[front()];
        }
    }
    
    return result;
}
 
// Benchmark comparison
function benchmark() {
    const n = 1_000_000;
    const k = 10_000;
    const nums = Array.from({ length: n }, () => Math.floor(Math.random() * 1000));
    
    console.time('Optimized');
    const result1 = maxSlidingWindowOptimized(nums, k);
    console.timeEnd('Optimized');
    
    // Compare with naive array-based deque 
    // (would be much slower due to shift())
}

Real-Time Systems

Beyond Sliding Windows: DP Optimization

The monotonic deque technique extends beyond simple sliding window max/min. One of its most powerful applications is optimizing dynamic programming recurrences.

The Pattern:

Many DP problems have recurrences of the form:

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

Naively, this is O(nk). But if cost(j, i) can be decomposed suitably, monotonic deque reduces it to O(n).

Example: Jump Game VI (LeetCode 1696)

Given nums[] and k, start at index 0.
At each position i, you can jump to any position in [i+1, i+k].
Score is sum of nums[] at visited positions.
Find maximum score to reach the end.

Recurrence:

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

The max(dp[j]) over a sliding window is exactly our problem!

jump_game_vi.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * LeetCode 1696: Jump Game VI
 * 
 * DP with monotonic deque optimization
 * Reduces O(nk) to O(n)
 */
function maxResult(nums: number[], k: number): number {
    const n = nums.length;
    const dp = new Array<number>(n);
    dp[0] = nums[0];
    
    // Deque stores indices, values (dp values) are decreasing
    const deque: number[] = [0];
    
    for (let i = 1; i < n; i++) {
        // Remove expired indices from front
        while (deque.length && deque[0] < i - k) {
            deque.shift();
        }
        
        // dp[i] = nums[i] + max(dp[j]) for j in window
        // The front of deque has the max dp[j]
        dp[i] = nums[i] + dp[deque[0]];
        
        // Remove dominated from back (dp values <= dp[i])
        while (deque.length && dp[deque[deque.length - 1]] <= dp[i]) {
            deque.pop();
        }
        
        // Add current index
        deque.push(i);
    }
    
    return dp[n - 1];
}
 
// Example
console.log(maxResult([1, -1, -2, 4, -7, 3], 2));
// Expected: 7 (path: 1 -> -1 -> 4 -> 3 = 7)
 
console.log(maxResult([10, -5, -2, 4, 0, 3], 3));
// Expected: 17 (path: 10 -> 4 -> 3 = 17)
 
console.log(maxResult([1, -5, -20, 4, -1, 3, -6, -3], 2));
// Expected: 0

The Power of Deque-Optimized DP

Summary: Mastering Monotonic Deque Complexity

We've completed our deep dive into the time complexity of the monotonic deque technique. Let's consolidate everything we've learned:

Key Takeaways

•O(n) Time Proven — Using aggregate analysis: each element is pushed once and popped at most once, giving 3n total operations.
•Amortized Analysis — Individual iterations may cost O(k), but total across all iterations is O(n). Don't be fooled by nested loops!
•Accounting Method — Prepay for future pops when you push. This mental model helps reason about complex amortized algorithms.
•O(k) Space — The deque holds at most k indices. Actual size varies by input pattern but never exceeds k.
•Optimal for Sliding Windows — Beats O(nk) naive by factor of k, beats O(n log k) heap by factor of log k.
•DP Optimization — The technique generalizes to optimize DP recurrences with sliding window maximum/minimum subproblems.

Module Complete: Sliding Window Maximum with Monotonic Deque

You've now mastered one of the most elegant and powerful techniques in competitive programming and algorithm design. The monotonic deque is:

Theoretically optimal — O(n) time, O(k) auxiliary space
Practically efficient — Simple to implement with good cache behavior
Widely applicable — Sliding windows, DP optimization, range queries
Fundamentally important — Teaches amortized analysis, invariant-based design

Module Complete

4 / 4