Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

3 / 4

Monotonic Deque Technique

From Specific Solution to General Technique

In the previous pages, we developed an intuition for maintaining candidate maximums using a deque. Now it's time to formalize this approach as a general technique with a precise name: the Monotonic Deque.

The word "monotonic" means "always increasing" or "always decreasing." A monotonic deque maintains elements in a specific order—either strictly increasing or strictly decreasing—which guarantees that the front element is always the extremum (minimum or maximum) we're tracking.

This isn't just an elegant solution to one problem; it's a powerful algorithmic tool that appears in dynamic programming optimizations, computational geometry, and advanced string algorithms. Mastering it opens doors to solving seemingly intractable problems efficiently.

What You Will Learn

By the end of this page, you will understand the monotonic deque as a formal technique: its definition, the invariants it maintains, the complete algorithm with edge cases, a rigorous proof of correctness, and how to apply it to both maximum and minimum variants.

What is a Monotonic Deque?

A monotonic deque is a deque that maintains its elements in either monotonically increasing or monotonically decreasing order. This ordering is preserved through careful insertion and deletion operations.

Definition:

A deque D = [d₀, d₁, d₂, ..., dₘ] is:

Monotonically Decreasing if D[0] ≥ D[1] ≥ D[2] ≥ ... ≥ D[m]
Monotonically Increasing if D[0] ≤ D[1] ≤ D[2] ≤ ... ≤ D[m]

For the sliding window maximum problem, we use a monotonically decreasing deque. This ensures the front element is always the maximum of all elements in the deque.

Decreasing Deque (For Maximum)

•Values decrease from front to back
•Front always holds the maximum
•New elements pop smaller elements from back
•Used for: sliding window maximum, histogram area

Increasing Deque (For Minimum)

•Values increase from front to back
•Front always holds the minimum
•New elements pop larger elements from back
•Used for: sliding window minimum, shortest subarray with sum ≥ k

Monotonic Stack vs Monotonic Deque

A monotonic stack is a special case of a monotonic deque that only uses one end (back operations). A monotonic deque adds front operations for scenarios like sliding windows where old elements expire. If you understand monotonic stacks, monotonic deques are a natural extension.

The Invariants We Maintain

The monotonic deque for sliding window maximum maintains three critical invariants at all times. Understanding these invariants is key to both implementing and proving the algorithm.

Invariant 1: Value Monotonicity

For all 0 ≤ i < j ≤ size(deque) - 1:
    nums[deque[i]] > nums[deque[j]]

Values are strictly decreasing from front to back (we use > not ≥ because we pop equal values too).

Invariant 2: Index Monotonicity

For all 0 ≤ i < j ≤ size(deque) - 1:
    deque[i] < deque[j]

Indices are strictly increasing from front to back.

Invariant 3: Window Containment

For all indices i in deque:
    i >= current_window_start

All stored indices are within the current window bounds.

Why These Invariants Matter:

Invariant	Purpose
Value Monotonicity	Ensures front is always the maximum
Index Monotonicity	Ensures we only check front for expiration
Window Containment	Ensures all candidates are valid for the current window

The Key Theorem:

Given invariants 1-3, the maximum element in the current window is always nums[deque.front()].

Proof:

By Invariant 3, all elements in the deque are within the window
By Invariant 1, the front element has the largest value
Any window element not in the deque was removed because a later, larger element dominates it
Therefore, the front is the maximum of the window ∎

Invariant-Driven Programming

Thinking in invariants transforms algorithm design. Instead of asking 'what operations do I do?', ask 'what properties must always be true, and what operations maintain them?' This mental model prevents bugs and makes correctness proofs natural.

The Complete Algorithm

Let's present the complete monotonic deque algorithm for sliding window maximum, handling all edge cases properly.

Algorithm Overview:

function slidingWindowMaximum(nums, k):
    deque = empty deque of indices
    result = []
    
    for i from 0 to n - 1:
        # Step 1: Maintain value monotonicity (remove dominated)
        while deque is not empty AND nums[deque.back()] <= nums[i]:
            deque.popBack()
        
        # Step 2: Add new candidate
        deque.pushBack(i)
        
        # Step 3: Maintain window containment (remove expired)
        while deque.front() < i - k + 1:
            deque.popFront()
        
        # Step 4: Record result (once window is full)
        if i >= k - 1:
            result.append(nums[deque.front()])
    
    return result

monotonic_deque_complete.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Sliding Window Maximum using Monotonic Deque
 * 
 * Time Complexity: O(n) - each element enters and exits deque at most once
 * Space Complexity: O(k) - deque holds at most k elements
 * 
 * @param nums - The input array
 * @param k - The window size
 * @returns Array of maximum values for each window
 */
function maxSlidingWindow(nums: number[], k: number): number[] {
    // Edge cases
    if (nums.length === 0 || k === 0) return [];
    if (k === 1) return [...nums];  // Each element is its own window's max
    if (k >= nums.length) return [Math.max(...nums)];  // Single window
    
    const n = nums.length;
    const result: number[] = new Array(n - k + 1);
    const deque: number[] = [];  // Stores indices, values are decreasing
    
    for (let i = 0; i < n; i++) {
        // Step 1: Remove dominated elements from the back
        // These elements can never be the maximum while nums[i] is in window
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }
        
        // Step 2: Add current index to the back
        deque.push(i);
        
        // Step 3: Remove expired elements from the front
        // Element is expired if index < i - k + 1 (outside current window)
        const windowStart = i - k + 1;
        while (deque[0] < windowStart) {
            deque.shift();  // Note: O(n) in JS, use proper Deque for efficiency
        }
        
        // Step 4: Record maximum for this window
        // Only record after we've filled the first window (i >= k - 1)
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque[0]];
        }
    }
    
    return result;
}
 
// Test cases
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Expected: [3, 3, 5, 5, 6, 7]
 
console.log(maxSlidingWindow([1], 1));
// Expected: [1]
 
console.log(maxSlidingWindow([1, -1], 1));
// Expected: [1, -1]
 
console.log(maxSlidingWindow([9, 11], 2));
// Expected: [11]
 
console.log(maxSlidingWindow([4, -2], 2));
// Expected: [4]

Edge Case Handling

Always handle edge cases explicitly: empty arrays, k=1, k≥n. While the main algorithm handles these correctly, explicit checks improve performance and make behavior clear. For k=1, every element is its own maximum. For k≥n, there's only one window.

Proof of Correctness

Let's rigorously prove that the monotonic deque algorithm correctly computes the sliding window maximum.

Theorem: For each window [i, i+k-1], the algorithm outputs max(nums[i], nums[i+1], ..., nums[i+k-1]).

Proof:

We prove by maintaining loop invariants. After processing index j, define:

W(j) = the window [max(0, j-k+1), j] (current window at position j)
D(j) = contents of deque after processing j

Loop Invariant: After processing index j:

D(j) contains indices of a subset of W(j)
Values in D(j) are strictly decreasing
The front of D(j) holds the maximum of W(j)

Base Case (j = 0):

W(0) = [0, 0] = {nums[0]}
D(0) = [0] (we push 0, nothing to remove)
nums[D(0)[0]] = nums[0] = max(W(0)) ✓

Inductive Step:

Assume invariant holds for j-1. We process j:

Step 1: Remove elements from back where nums[back] ≤ nums[j]

These elements cannot be maximum while j is in window (j is ≥ and later)
Removing them preserves the decreasing property

Step 2: Add j to back

After Step 1, back > nums[j] or deque is empty
Adding j maintains decreasing property

Step 3: Remove expired elements from front

Remove indices < j - k + 1 (outside current window)
Since indices increase front-to-back, we only check front

Step 4: The maximum of W(j)

Front of deque is the largest remaining value
All window elements are either in deque OR were dominated by a deque element
Therefore, front = max(W(j)) ✓

The Domination Lemma

The key insight is the Domination Lemma: If nums[i] ≤ nums[j] and i < j, then nums[i] can never be the maximum of any window containing both i and j. This justifies removing dominated elements without losing the ability to find the maximum.

Completeness Argument:

We must also show that the maximum is never incorrectly removed:

Dominated removal: An element is only removed from the back if a larger (or equal) element exists to its right. That larger element will represent the maximum instead.
Expiration removal: An element is only removed from the front when it exits the window. By definition, it can't be the current window's maximum.

Therefore, the true maximum is always preserved in the deque until it naturally expires. ∎

The Minimum Variant

The sliding window minimum problem is solved by simply reversing the comparison. Instead of a monotonically decreasing deque, we maintain a monotonically increasing deque.

Changes from Maximum to Minimum:

Maximum Version	Minimum Version
Remove if back ≤ current	Remove if back ≥ current
Decreasing order	Increasing order
Front is largest	Front is smallest

sliding_window_minimum.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
46
47
48
49
/**
 * Sliding Window Minimum using Monotonic Deque (Increasing)
 * 
 * The only change from maximum: use >= instead of <= when removing
 * This maintains an increasing order, so front is always minimum
 */
function minSlidingWindow(nums: number[], k: number): number[] {
    if (nums.length === 0 || k === 0) return [];
    if (k === 1) return [...nums];
    
    const n = nums.length;
    const result: number[] = new Array(n - k + 1);
    const deque: number[] = [];  // Stores indices, values are INCREASING
    
    for (let i = 0; i < n; i++) {
        // Remove elements >= current (they can't be minimum anymore)
        // Changed from <= to >= compared to maximum version
        while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
            deque.pop();
        }
        
        deque.push(i);
        
        // Remove expired elements (same as maximum version)
        const windowStart = i - k + 1;
        while (deque[0] < windowStart) {
            deque.shift();
        }
        
        // Record minimum
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque[0]];
        }
    }
    
    return result;
}
 
// Example
console.log(minSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Expected: [-1, -3, -3, -3, 3, 3]
 
// Trace for k=3:
// Window [1, 3, -1]  →  min = -1
// Window [3, -1, -3] →  min = -3
// Window [-1, -3, 5] →  min = -3
// Window [-3, 5, 3]  →  min = -3
// Window [5, 3, 6]   →  min = 3
// Window [3, 6, 7]   →  min = 3

Pattern Recognition

Maximum → Decreasing deque (remove smaller/equal). Minimum → Increasing deque (remove larger/equal). The direction of the comparison and the monotonicity always match the extremum you're tracking.

Advanced: Tracking Both Max and Min

Some problems require tracking both the maximum and minimum simultaneously in each window. A classic example is LeetCode 1438: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.

Problem: Find the longest subarray where max - min ≤ limit.

Approach: Use TWO monotonic deques—one for maximum, one for minimum—and expand/contract a sliding window.

longest_subarray_with_limit.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
46
47
48
49
50
51
52
53
/**
 * LeetCode 1438: Longest Continuous Subarray With Absolute Diff <= Limit
 * 
 * Uses two monotonic deques to track max and min simultaneously
 * Combined with a sliding window that expands/contracts
 */
function longestSubarray(nums: number[], limit: number): number {
    const maxDeque: number[] = [];  // Decreasing - front is max
    const minDeque: number[] = [];  // Increasing - front is min
    
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Add nums[right] to both deques
        
        // Max deque: remove smaller elements
        while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
            maxDeque.pop();
        }
        maxDeque.push(right);
        
        // Min deque: remove larger elements
        while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
            minDeque.pop();
        }
        minDeque.push(right);
        
        // Contract window if diff exceeds limit
        while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
            left++;
            
            // Remove expired elements from both deques
            if (maxDeque[0] < left) maxDeque.shift();
            if (minDeque[0] < left) minDeque.shift();
        }
        
        // Update maximum length
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}
 
// Example
console.log(longestSubarray([8, 2, 4, 7], 4));
// Expected: 2 (subarray [2, 4] has max-min = 2 <= 4)
 
console.log(longestSubarray([10, 1, 2, 4, 7, 2], 5));
// Expected: 4 (subarray [2, 4, 7, 2] has max 7, min 2, diff = 5)
 
console.log(longestSubarray([4, 2, 2, 2, 4, 4, 2, 2], 0));
// Expected: 3 (subarray [2, 2, 2] has max=min=2, diff = 0)

Two Deques Pattern

Using two monotonic deques (one for max, one for min) is a powerful pattern. It allows O(1) access to both extremes of any sliding window. This pattern appears in constrained subarray problems, range query optimization, and streaming algorithms.

Generalization: The Monotonic Deque Framework

The monotonic deque technique can be generalized to solve any problem fitting this template:

Problem Template:

Given a sequence and a window constraint, efficiently compute some function where:

The function depends on an extremum (min/max) over the window
Windows overlap significantly (adjacent windows share most elements)
We process windows in order (sliding left to right)

The General Algorithm:

function monotonDequeTemplate(sequence, windowConstraint, compareFn):
    deque = []
    
    for each element with index i:
        # Remove dominated elements (based on compareFn)
        while deque not empty AND compare(back, element) is unfavorable:
            popBack()
        
        # Add new element
        pushBack(i)
        
        # Remove expired elements
        while front is outside window:
            popFront()
        
        # Use front for current window's answer
        process(front)

Monotonic Deque Problem Categories
Category	Example Problems	Deque Type
Fixed Window Extremum	Sliding Window Max/Min	Decreasing/Increasing
Variable Window Constraint	Longest Subarray with Limit	Two Deques
DP Optimization	Jump Game VI, Constrained Subsequence Sum	Decreasing (track best)
Prefix Sum + Deque	Shortest Subarray with Sum ≥ K	Increasing
Geometric/Range	Largest Rectangle in Histogram	Monotonic Stack variant

When to Use Monotonic Deque

Consider monotonic deque when: (1) You need extremum over sliding ranges, (2) Processing windows in order, (3) Naive approach is O(nk) or O(n²), (4) You see 'maximum/minimum' combined with 'subarray of length k' or 'within distance k'. The technique often reduces O(nk) to O(n) or optimizes DP from O(n²) to O(n).

Summary and What's Next

We've formalized the monotonic deque technique into a powerful algorithmic tool. Let's consolidate the key concepts:

Key Takeaways

•Monotonic Deque Definition — A deque maintaining elements in strictly increasing or decreasing order, with the front always holding the extremum.
•Three Invariants — Value monotonicity, index monotonicity, and window containment together guarantee correctness.
•The Complete Algorithm — Remove dominated from back, add new, remove expired from front, read from front.
•Proved Correct — The Domination Lemma ensures we never remove the true maximum prematurely.
•Dual Application — Use decreasing deque for maximum, increasing deque for minimum.
•Advanced Patterns — Two deques for simultaneous max/min, DP optimization, prefix sum combinations.

What's Next:

In the final page of this module, we'll conduct a rigorous time complexity analysis of the monotonic deque approach. We'll prove the O(n) bound, understand amortized analysis, compare against alternative approaches, and discuss the space-time tradeoffs. This completes your mastery of this powerful technique.

Page Complete

You now understand the monotonic deque as a formal technique: its definition, invariants, complete algorithm, correctness proof, and applications to both maximum and minimum problems. You're ready to analyze why this achieves optimal O(n) time complexity.

3 / 4

Loading learning content...

Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

3 / 4

Monotonic Deque Technique

From Specific Solution to General Technique

What You Will Learn

What is a Monotonic Deque?

Definition:

A deque D = [d₀, d₁, d₂, ..., dₘ] is:

Monotonically Decreasing if D[0] ≥ D[1] ≥ D[2] ≥ ... ≥ D[m]
Monotonically Increasing if D[0] ≤ D[1] ≤ D[2] ≤ ... ≤ D[m]

For the sliding window maximum problem, we use a monotonically decreasing deque. This ensures the front element is always the maximum of all elements in the deque.

Decreasing Deque (For Maximum)

•Values decrease from front to back
•Front always holds the maximum
•New elements pop smaller elements from back
•Used for: sliding window maximum, histogram area

Increasing Deque (For Minimum)

•Values increase from front to back
•Front always holds the minimum
•New elements pop larger elements from back
•Used for: sliding window minimum, shortest subarray with sum ≥ k

Monotonic Stack vs Monotonic Deque

The Invariants We Maintain

The monotonic deque for sliding window maximum maintains three critical invariants at all times. Understanding these invariants is key to both implementing and proving the algorithm.

Invariant 1: Value Monotonicity

For all 0 ≤ i < j ≤ size(deque) - 1:
    nums[deque[i]] > nums[deque[j]]

Values are strictly decreasing from front to back (we use > not ≥ because we pop equal values too).

Invariant 2: Index Monotonicity

For all 0 ≤ i < j ≤ size(deque) - 1:
    deque[i] < deque[j]

Indices are strictly increasing from front to back.

Invariant 3: Window Containment

For all indices i in deque:
    i >= current_window_start

All stored indices are within the current window bounds.

Why These Invariants Matter:

Invariant	Purpose
Value Monotonicity	Ensures front is always the maximum
Index Monotonicity	Ensures we only check front for expiration
Window Containment	Ensures all candidates are valid for the current window

The Key Theorem:

Given invariants 1-3, the maximum element in the current window is always nums[deque.front()].

Proof:

By Invariant 3, all elements in the deque are within the window
By Invariant 1, the front element has the largest value
Any window element not in the deque was removed because a later, larger element dominates it
Therefore, the front is the maximum of the window ∎

Invariant-Driven Programming

The Complete Algorithm

Let's present the complete monotonic deque algorithm for sliding window maximum, handling all edge cases properly.

Algorithm Overview:

function slidingWindowMaximum(nums, k):
    deque = empty deque of indices
    result = []
    
    for i from 0 to n - 1:
        # Step 1: Maintain value monotonicity (remove dominated)
        while deque is not empty AND nums[deque.back()] <= nums[i]:
            deque.popBack()
        
        # Step 2: Add new candidate
        deque.pushBack(i)
        
        # Step 3: Maintain window containment (remove expired)
        while deque.front() < i - k + 1:
            deque.popFront()
        
        # Step 4: Record result (once window is full)
        if i >= k - 1:
            result.append(nums[deque.front()])
    
    return result

monotonic_deque_complete.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Sliding Window Maximum using Monotonic Deque
 * 
 * Time Complexity: O(n) - each element enters and exits deque at most once
 * Space Complexity: O(k) - deque holds at most k elements
 * 
 * @param nums - The input array
 * @param k - The window size
 * @returns Array of maximum values for each window
 */
function maxSlidingWindow(nums: number[], k: number): number[] {
    // Edge cases
    if (nums.length === 0 || k === 0) return [];
    if (k === 1) return [...nums];  // Each element is its own window's max
    if (k >= nums.length) return [Math.max(...nums)];  // Single window
    
    const n = nums.length;
    const result: number[] = new Array(n - k + 1);
    const deque: number[] = [];  // Stores indices, values are decreasing
    
    for (let i = 0; i < n; i++) {
        // Step 1: Remove dominated elements from the back
        // These elements can never be the maximum while nums[i] is in window
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }
        
        // Step 2: Add current index to the back
        deque.push(i);
        
        // Step 3: Remove expired elements from the front
        // Element is expired if index < i - k + 1 (outside current window)
        const windowStart = i - k + 1;
        while (deque[0] < windowStart) {
            deque.shift();  // Note: O(n) in JS, use proper Deque for efficiency
        }
        
        // Step 4: Record maximum for this window
        // Only record after we've filled the first window (i >= k - 1)
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque[0]];
        }
    }
    
    return result;
}
 
// Test cases
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Expected: [3, 3, 5, 5, 6, 7]
 
console.log(maxSlidingWindow([1], 1));
// Expected: [1]
 
console.log(maxSlidingWindow([1, -1], 1));
// Expected: [1, -1]
 
console.log(maxSlidingWindow([9, 11], 2));
// Expected: [11]
 
console.log(maxSlidingWindow([4, -2], 2));
// Expected: [4]

Edge Case Handling

Proof of Correctness

Let's rigorously prove that the monotonic deque algorithm correctly computes the sliding window maximum.

Theorem: For each window [i, i+k-1], the algorithm outputs max(nums[i], nums[i+1], ..., nums[i+k-1]).

Proof:

We prove by maintaining loop invariants. After processing index j, define:

W(j) = the window [max(0, j-k+1), j] (current window at position j)
D(j) = contents of deque after processing j

Loop Invariant: After processing index j:

D(j) contains indices of a subset of W(j)
Values in D(j) are strictly decreasing
The front of D(j) holds the maximum of W(j)

Base Case (j = 0):

W(0) = [0, 0] = {nums[0]}
D(0) = [0] (we push 0, nothing to remove)
nums[D(0)[0]] = nums[0] = max(W(0)) ✓

Inductive Step:

Assume invariant holds for j-1. We process j:

Step 1: Remove elements from back where nums[back] ≤ nums[j]

These elements cannot be maximum while j is in window (j is ≥ and later)
Removing them preserves the decreasing property

Step 2: Add j to back

After Step 1, back > nums[j] or deque is empty
Adding j maintains decreasing property

Step 3: Remove expired elements from front

Remove indices < j - k + 1 (outside current window)
Since indices increase front-to-back, we only check front

Step 4: The maximum of W(j)

Front of deque is the largest remaining value
All window elements are either in deque OR were dominated by a deque element
Therefore, front = max(W(j)) ✓

The Domination Lemma

Completeness Argument:

We must also show that the maximum is never incorrectly removed:

Dominated removal: An element is only removed from the back if a larger (or equal) element exists to its right. That larger element will represent the maximum instead.
Expiration removal: An element is only removed from the front when it exits the window. By definition, it can't be the current window's maximum.

Therefore, the true maximum is always preserved in the deque until it naturally expires. ∎

The Minimum Variant

The sliding window minimum problem is solved by simply reversing the comparison. Instead of a monotonically decreasing deque, we maintain a monotonically increasing deque.

Changes from Maximum to Minimum:

Maximum Version	Minimum Version
Remove if back ≤ current	Remove if back ≥ current
Decreasing order	Increasing order
Front is largest	Front is smallest

sliding_window_minimum.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
46
47
48
49
/**
 * Sliding Window Minimum using Monotonic Deque (Increasing)
 * 
 * The only change from maximum: use >= instead of <= when removing
 * This maintains an increasing order, so front is always minimum
 */
function minSlidingWindow(nums: number[], k: number): number[] {
    if (nums.length === 0 || k === 0) return [];
    if (k === 1) return [...nums];
    
    const n = nums.length;
    const result: number[] = new Array(n - k + 1);
    const deque: number[] = [];  // Stores indices, values are INCREASING
    
    for (let i = 0; i < n; i++) {
        // Remove elements >= current (they can't be minimum anymore)
        // Changed from <= to >= compared to maximum version
        while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
            deque.pop();
        }
        
        deque.push(i);
        
        // Remove expired elements (same as maximum version)
        const windowStart = i - k + 1;
        while (deque[0] < windowStart) {
            deque.shift();
        }
        
        // Record minimum
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque[0]];
        }
    }
    
    return result;
}
 
// Example
console.log(minSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Expected: [-1, -3, -3, -3, 3, 3]
 
// Trace for k=3:
// Window [1, 3, -1]  →  min = -1
// Window [3, -1, -3] →  min = -3
// Window [-1, -3, 5] →  min = -3
// Window [-3, 5, 3]  →  min = -3
// Window [5, 3, 6]   →  min = 3
// Window [3, 6, 7]   →  min = 3

Pattern Recognition

Advanced: Tracking Both Max and Min

Problem: Find the longest subarray where max - min ≤ limit.

Approach: Use TWO monotonic deques—one for maximum, one for minimum—and expand/contract a sliding window.

longest_subarray_with_limit.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
46
47
48
49
50
51
52
53
/**
 * LeetCode 1438: Longest Continuous Subarray With Absolute Diff <= Limit
 * 
 * Uses two monotonic deques to track max and min simultaneously
 * Combined with a sliding window that expands/contracts
 */
function longestSubarray(nums: number[], limit: number): number {
    const maxDeque: number[] = [];  // Decreasing - front is max
    const minDeque: number[] = [];  // Increasing - front is min
    
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Add nums[right] to both deques
        
        // Max deque: remove smaller elements
        while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
            maxDeque.pop();
        }
        maxDeque.push(right);
        
        // Min deque: remove larger elements
        while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
            minDeque.pop();
        }
        minDeque.push(right);
        
        // Contract window if diff exceeds limit
        while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
            left++;
            
            // Remove expired elements from both deques
            if (maxDeque[0] < left) maxDeque.shift();
            if (minDeque[0] < left) minDeque.shift();
        }
        
        // Update maximum length
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}
 
// Example
console.log(longestSubarray([8, 2, 4, 7], 4));
// Expected: 2 (subarray [2, 4] has max-min = 2 <= 4)
 
console.log(longestSubarray([10, 1, 2, 4, 7, 2], 5));
// Expected: 4 (subarray [2, 4, 7, 2] has max 7, min 2, diff = 5)
 
console.log(longestSubarray([4, 2, 2, 2, 4, 4, 2, 2], 0));
// Expected: 3 (subarray [2, 2, 2] has max=min=2, diff = 0)

Two Deques Pattern

Generalization: The Monotonic Deque Framework

The monotonic deque technique can be generalized to solve any problem fitting this template:

Problem Template:

Given a sequence and a window constraint, efficiently compute some function where:

The function depends on an extremum (min/max) over the window
Windows overlap significantly (adjacent windows share most elements)
We process windows in order (sliding left to right)

The General Algorithm:

function monotonDequeTemplate(sequence, windowConstraint, compareFn):
    deque = []
    
    for each element with index i:
        # Remove dominated elements (based on compareFn)
        while deque not empty AND compare(back, element) is unfavorable:
            popBack()
        
        # Add new element
        pushBack(i)
        
        # Remove expired elements
        while front is outside window:
            popFront()
        
        # Use front for current window's answer
        process(front)

Monotonic Deque Problem Categories
Category	Example Problems	Deque Type
Fixed Window Extremum	Sliding Window Max/Min	Decreasing/Increasing
Variable Window Constraint	Longest Subarray with Limit	Two Deques
DP Optimization	Jump Game VI, Constrained Subsequence Sum	Decreasing (track best)
Prefix Sum + Deque	Shortest Subarray with Sum ≥ K	Increasing
Geometric/Range	Largest Rectangle in Histogram	Monotonic Stack variant

When to Use Monotonic Deque

Summary and What's Next

We've formalized the monotonic deque technique into a powerful algorithmic tool. Let's consolidate the key concepts:

Key Takeaways

•Monotonic Deque Definition — A deque maintaining elements in strictly increasing or decreasing order, with the front always holding the extremum.
•Three Invariants — Value monotonicity, index monotonicity, and window containment together guarantee correctness.
•The Complete Algorithm — Remove dominated from back, add new, remove expired from front, read from front.
•Proved Correct — The Domination Lemma ensures we never remove the true maximum prematurely.
•Dual Application — Use decreasing deque for maximum, increasing deque for minimum.
•Advanced Patterns — Two deques for simultaneous max/min, DP optimization, prefix sum combinations.

What's Next:

Page Complete

3 / 4