The Sliding Window Maximum Problem - Sliding Window Maximum — Monotonic Deque | OneNoughtOne

Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

1 / 4

The Sliding Window Maximum Problem

A Classic Problem in Algorithmic Design

Imagine you're building a real-time stock trading system. Every second, you receive a new stock price, and you need to display the maximum price over the last 60 seconds. As new prices arrive, old prices fall outside your window, and you must continuously update the maximum.

This is the sliding window maximum problem—one of the most elegant problems in algorithmic design that sits at the intersection of array processing, window techniques, and specialized data structures. It appears in countless real-world applications: monitoring systems, signal processing, financial analytics, and gaming leaderboards.

What makes this problem fascinating is that the naive approach is deceptively simple, yet achieving optimal efficiency requires a profound insight about how we track and discard candidate values.

What You Will Learn

By the end of this page, you will deeply understand the sliding window maximum problem—its formal definition, why it matters in practice, why naive approaches fail at scale, and why we need a specialized technique to solve it efficiently. This foundation is essential before we introduce the monotonic deque solution.

Problem Definition

Let's establish the problem formally before exploring solutions.

The Sliding Window Maximum Problem:

Given an array nums of n elements and a window size k, find the maximum element in every contiguous subarray (window) of size k.

Input:

An array nums = [a₀, a₁, a₂, ..., aₙ₋₁] of n elements
A positive integer k where 1 ≤ k ≤ n

Output:

An array of n - k + 1 elements, where the i-th element is the maximum of nums[i..i+k-1]

Example:

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

Window positions:                Maximum:
[1  3  -1] -3  5  3  6  7        3
 1 [3  -1  -3] 5  3  6  7        3
 1  3 [-1  -3  5] 3  6  7        5
 1  3  -1 [-3  5  3] 6  7        5
 1  3  -1  -3 [5  3  6] 7        6
 1  3  -1  -3  5 [3  6  7]       7

Output: [3, 3, 5, 5, 6, 7]

The Sliding Nature

The key insight is that the window slides one position at a time. When moving from window [i, i+k-1] to [i+1, i+k], exactly one element (nums[i]) leaves the window and exactly one element (nums[i+k]) enters. This incremental change is what makes optimization possible—we shouldn't need to recompute the maximum from scratch each time.

Constraints to Consider:

In competitive programming and real-world systems, you'll encounter various constraint ranges:

Constraint Level	n range	k range	Implications
Small	n ≤ 10³	k ≤ n	Naive O(nk) is acceptable
Medium	n ≤ 10⁵	k ≤ n	Need O(n log k) or better
Large	n ≤ 10⁶	k ≤ n	Must achieve O(n)
Extreme	n ≤ 10⁷	k ≤ n	O(n) with low constant factor

This module focuses on achieving the optimal O(n) solution that works across all constraint levels.

Why This Problem Matters

The sliding window maximum problem isn't merely an academic exercise—it represents a fundamental pattern that appears throughout software engineering and algorithm design. Understanding this problem deeply equips you with techniques applicable far beyond the specific problem statement.

Real-World Applications

•Financial Systems — Calculate rolling maximum stock prices, identify peak values in trading windows, detect price anomalies over time periods.
•Monitoring & Alerting — Track maximum CPU usage, memory consumption, or latency over sliding time windows for alerting thresholds.
•Signal Processing — Find peak amplitudes in audio signals, detect maximum intensity in sensor readings, process streaming data.
•Gaming & Leaderboards — Maintain top scores over recent time periods, track maximum achievements in rolling windows.
•Network Analysis — Monitor peak bandwidth usage, track maximum packet rates, detect traffic spikes in time windows.
•Database Query Optimization — Certain analytic queries (ROWS BETWEEN PRECEDING) reduce to sliding window problems internally.

The Pattern Recognition Value:

Beyond direct applications, this problem teaches a critical pattern: how to efficiently maintain aggregate information (maximum, minimum, sum) over a sliding window. Once you master the monotonic deque technique here, you can apply similar reasoning to:

Sliding window minimum
Sliding window with arbitrary width
Multiple simultaneous sliding windows
Window-based range queries
Stream processing with bounded memory

This pattern appears in LeetCode problems, system design interviews, and production code alike.

Interview Significance

The sliding window maximum problem is a favorite at FAANG companies because it tests multiple skills simultaneously: understanding the problem constraints, recognizing that naive solutions won't scale, knowledge of specialized data structures, and ability to reason about amortized complexity. Mastering this problem signals algorithmic maturity.

The Naive Approach

Before optimizing, let's understand the straightforward approach and analyze why it falls short.

The Brute Force Algorithm:

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

function slidingWindowMaxNaive(nums, k):
    n = length(nums)
    result = new array of size (n - k + 1)
    
    for i from 0 to n - k:
        maxVal = nums[i]
        for j from i + 1 to i + k - 1:
            if nums[j] > maxVal:
                maxVal = nums[j]
        result[i] = maxVal
    
    return result

This approach is intuitive and correct. For each of the n - k + 1 windows, we perform k comparisons.

naive_sliding_window_max.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
function maxSlidingWindowNaive(nums: number[], k: number): number[] {
    const n = nums.length;
    const result: number[] = [];
    
    // For each window starting position
    for (let i = 0; i <= n - k; i++) {
        let maxVal = nums[i];
        
        // Scan all k elements in the window
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] > maxVal) {
                maxVal = nums[j];
            }
        }
        
        result.push(maxVal);
    }
    
    return result;
}
 
// Example usage
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindowNaive(nums, k)); 
// Output: [3, 3, 5, 5, 6, 7]

Complexity Analysis:

Aspect	Complexity	Explanation
Time	O(n × k)	For each of (n-k+1) windows, scan k elements
Space	O(n - k + 1)	Output array storage

Why This Fails at Scale:

Consider the worst-case scenarios for large inputs:

n = 10⁶, k = 10³: 10⁶ × 10³ = 10⁹ operations (~1 second just for comparisons)
n = 10⁶, k = 10⁵: 10⁶ × 10⁵ = 10¹¹ operations (~100 seconds)
n = 10⁶, k = 5×10⁵: 10⁶ × 5×10⁵ = 5×10¹¹ operations (~500 seconds)

For real-time systems processing millions of data points with large windows, this approach is completely impractical.

The Redundancy Problem

The fundamental issue is that we're doing redundant work. When the window slides from position i to i+1, we throw away all knowledge about the previous window and start fresh. But the windows [i, i+k-1] and [i+1, i+k] share k-1 elements! We should be able to leverage this overlap instead of recomputing from scratch.

Attempted Optimizations That Fall Short

Before arriving at the optimal solution, let's explore some natural optimization attempts and understand why they don't quite work. This analysis builds intuition for what the correct approach must achieve.

Optimization Attempt 1: Track the Current Maximum

•Idea: Keep track of the current maximum and update it as elements enter/leave the window.
•Adding elements: Easy! If new element > current max, update max.
•Removing elements: Problem! If the leaving element IS the maximum, what's the new maximum?
•Result: We'd need to rescan the entire window to find the new max → back to O(k) per removal.

The tracking approach fails because maximum is not an incrementally reducible operation. Unlike sum (where removing x means subtracting x), finding a new maximum after removing the current maximum requires examining all remaining candidates.

Optimization Attempt 2: Use a Sorted Data Structure

•Idea: Maintain elements in a balanced BST or sorted set. Maximum is always accessible in O(1) or O(log k).
•Adding elements: O(log k) insertion into the balanced structure.
•Removing elements: O(log k) deletion from the balanced structure.
•Total complexity: O(n log k) — better than O(nk), but not optimal.
•Issue: Doesn't leverage the specific sliding nature of the problem.

heap_based_approach.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
// Using a max-heap with lazy deletion
// This achieves O(n log k) but not O(n)
 
import { MaxPriorityQueue } from '@datastructures-js/priority-queue';
 
function maxSlidingWindowHeap(nums: number[], k: number): number[] {
    const result: number[] = [];
    // Store [value, index] pairs in max-heap
    const maxHeap = new MaxPriorityQueue<[number, number]>({
        compare: (a, b) => b[0] - a[0] // Max by value
    });
    
    for (let i = 0; i < nums.length; i++) {
        // Add new element
        maxHeap.enqueue([nums[i], i]);
        
        // Remove elements outside window (lazy deletion)
        while (maxHeap.front()[1] <= i - k) {
            maxHeap.dequeue();
        }
        
        // Once we have k elements, record maximum
        if (i >= k - 1) {
            result.push(maxHeap.front()[0]);
        }
    }
    
    return result;
}
 
// Complexity: O(n log k) time, O(k) space
// Better than naive, but can we do better?

The O(n log k) Heap-Based Approach:

Using a max-heap with lazy deletion, we can achieve O(n log k) time:

Insert each element with its index: O(log k)
Remove stale elements (outside window) from heap top: amortized O(log k)
Query maximum: O(1)

This is a valid solution for medium-sized inputs, but for truly large inputs (n = 10⁷, k = 10⁶), the log factor becomes significant.

The Question Remains:

Can we do better than O(n log k)? Can we achieve O(n) time regardless of window size?

The answer is yes—using a technique called the monotonic deque.

The Key Insight Preview

The breakthrough comes from realizing we don't need to track ALL elements in the window—only those that COULD POTENTIALLY become the maximum. Many elements enter the window but can never be the answer because a larger element entered after them and will leave after them. We can safely ignore these "dominated" elements.

Visualizing the Problem

Let's trace through a detailed example to build intuition for what candidates matter and which can be discarded.

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

Window-by-Window Analysis
Step	Window	Elements	Maximum	Key Observation
1	[0,2]	[1, 3, -1]	3	3 dominates 1 and -1 (later, larger)
2	[1,3]	[3, -1, -3]	3	3 still in window, still maximum
3	[2,4]	[-1, -3, 5]	5	5 enters and dominates everything
4	[3,5]	[-3, 5, 3]	5	5 still in window; 3 can't beat it
5	[4,6]	[5, 3, 6]	6	6 enters and dominates 5 and 3
6	[5,7]	[3, 6, 7]	7	7 enters and becomes new maximum

Critical Observation — The Domination Principle:

When element nums[j] enters the window, consider any earlier element nums[i] where i < j:

If nums[i] ≤ nums[j]: Element nums[i] can never be the maximum while nums[j] is in the window
Why? Because nums[j] entered later and is at least as large
When nums[i] leaves the window, nums[j] will still be there (since j > i)
Therefore, nums[i] is "dominated" and can be discarded

Example Trace:

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

i=0: See 1. Window: [1]. Candidates: [1]
i=1: See 3. 3 > 1, so 1 is dominated. Candidates: [3]
i=2: See -1. -1 < 3, keep both. Candidates: [3, -1]
     Window complete! Max = 3

i=3: See -3. -3 < -1, keep all. Candidates: [3, -1, -3]
     But wait! 3's index is 1, window starts at 1. OK.
     Max = 3

i=4: See 5. 5 > -3, 5 > -1, 5 > 3! All dominated.
     Candidates: [5]
     3's index was 1, now outside window [2,4]. Would remove anyway.
     Max = 5

i=5: See 3. 3 < 5, keep both. Candidates: [5, 3]
     Max = 5

i=6: See 6. 6 > 3, 6 > 5! Candidates: [6]
     Max = 6

i=7: See 7. 7 > 6! Candidates: [7]
     Max = 7

The Key Insight

At any point, we only need to maintain candidates in DECREASING order. When a new element arrives, we remove all candidates smaller than it (they're dominated). What remains is a decreasing sequence where the front is always the maximum. This is exactly what a monotonic deque provides!

Problem Variants and Extensions

The sliding window maximum problem has several important variants. Understanding these variants helps you recognize the pattern in different contexts and apply the same technique.

Common Problem Variants
Variant	Description	Modification Needed
Sliding Window Minimum	Find minimum instead of maximum	Use monotonically increasing deque
Variable Window Size	Window size changes over time	Track entry times, check bounds dynamically
Multiple Windows	Track max for windows of sizes k₁, k₂, ...	Use separate deques or segment trees
2D Sliding Window	Max in k×k rectangle sliding over matrix	Apply 1D technique row-wise, then column-wise
Circular Array	Array wraps around	Double the array or use modular arithmetic
Weighted Maximum	Elements have weights affecting priority	Combine with priority queue techniques

Common LeetCode Problems Using This Technique:

Problem	Difficulty	Core Technique
Sliding Window Maximum	Hard	Direct application
Longest Subarray with Abs Diff ≤ Limit	Medium	Two monotonic deques
Shortest Subarray with Sum ≥ K	Hard	Monotonic deque with prefix sums
Max Value of Equation	Hard	Monotonic deque optimization
Jump Game VI	Medium	DP with monotonic deque
Max Number of Robots	Hard	Monotonic deque + binary search

Mastering the base problem prepares you for all these variations.

The Sliding Window + Deque Pattern

Once you recognize this pattern, you'll see it everywhere. Any time you need to track an extremum (max/min) or monotonic property over a sliding window, a monotonic deque is likely the optimal approach. This single technique unlocks dozens of seemingly unrelated problems.

Summary and What's Next

We've established a solid foundation for understanding the sliding window maximum problem. Let's consolidate what we've learned:

Key Takeaways

•Problem Definition — Given an array and window size k, find the maximum in every window of size k as it slides across the array.
•Naive Approach — O(nk) time by scanning each window independently; fails at scale for large n and k.
•Why Simple Tracking Fails — Maximum is not incrementally reducible; when the max leaves, we can't easily determine the new max.
•Heap-Based Approach — O(n log k) using a max-heap with lazy deletion; better but not optimal.
•The Domination Insight — Elements that are smaller than later elements can never become the maximum while those later elements are in the window.
•What We Need — A data structure that maintains candidates in decreasing order and supports efficient front/back operations: a monotonic deque.

What's Next:

In the next page, we'll introduce the deque (double-ended queue) as our tool for maintaining candidate maximum values. We'll see how a deque's ability to efficiently add/remove from both ends perfectly matches the requirements of our sliding window problem.

We'll explore:

What makes a deque different from a regular queue or stack
Why a deque is essential for this problem
How to use a deque to maintain only the relevant candidates

Page Complete

You now understand the sliding window maximum problem, why naive approaches fail, and the key insight about element domination. This foundation prepares you for the elegant monotonic deque solution coming next.

1 / 4

Loading learning content...

Data Structures & AlgorithmsSliding Window Maximum

Sliding Window Maximum — Monotonic Deque

LevelIntermediate

Duration60 mins

TopicSliding Window Maximum

1 / 4

The Sliding Window Maximum Problem

A Classic Problem in Algorithmic Design

What makes this problem fascinating is that the naive approach is deceptively simple, yet achieving optimal efficiency requires a profound insight about how we track and discard candidate values.

What You Will Learn

Problem Definition

Let's establish the problem formally before exploring solutions.

The Sliding Window Maximum Problem:

Given an array nums of n elements and a window size k, find the maximum element in every contiguous subarray (window) of size k.

Input:

An array nums = [a₀, a₁, a₂, ..., aₙ₋₁] of n elements
A positive integer k where 1 ≤ k ≤ n

Output:

An array of n - k + 1 elements, where the i-th element is the maximum of nums[i..i+k-1]

Example:

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

Window positions:                Maximum:
[1  3  -1] -3  5  3  6  7        3
 1 [3  -1  -3] 5  3  6  7        3
 1  3 [-1  -3  5] 3  6  7        5
 1  3  -1 [-3  5  3] 6  7        5
 1  3  -1  -3 [5  3  6] 7        6
 1  3  -1  -3  5 [3  6  7]       7

Output: [3, 3, 5, 5, 6, 7]

The Sliding Nature

Constraints to Consider:

In competitive programming and real-world systems, you'll encounter various constraint ranges:

Constraint Level	n range	k range	Implications
Small	n ≤ 10³	k ≤ n	Naive O(nk) is acceptable
Medium	n ≤ 10⁵	k ≤ n	Need O(n log k) or better
Large	n ≤ 10⁶	k ≤ n	Must achieve O(n)
Extreme	n ≤ 10⁷	k ≤ n	O(n) with low constant factor

This module focuses on achieving the optimal O(n) solution that works across all constraint levels.

Why This Problem Matters

Real-World Applications

•Financial Systems — Calculate rolling maximum stock prices, identify peak values in trading windows, detect price anomalies over time periods.
•Monitoring & Alerting — Track maximum CPU usage, memory consumption, or latency over sliding time windows for alerting thresholds.
•Signal Processing — Find peak amplitudes in audio signals, detect maximum intensity in sensor readings, process streaming data.
•Gaming & Leaderboards — Maintain top scores over recent time periods, track maximum achievements in rolling windows.
•Network Analysis — Monitor peak bandwidth usage, track maximum packet rates, detect traffic spikes in time windows.
•Database Query Optimization — Certain analytic queries (ROWS BETWEEN PRECEDING) reduce to sliding window problems internally.

The Pattern Recognition Value:

Sliding window minimum
Sliding window with arbitrary width
Multiple simultaneous sliding windows
Window-based range queries
Stream processing with bounded memory

This pattern appears in LeetCode problems, system design interviews, and production code alike.

Interview Significance

The Naive Approach

Before optimizing, let's understand the straightforward approach and analyze why it falls short.

The Brute Force Algorithm:

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

function slidingWindowMaxNaive(nums, k):
    n = length(nums)
    result = new array of size (n - k + 1)
    
    for i from 0 to n - k:
        maxVal = nums[i]
        for j from i + 1 to i + k - 1:
            if nums[j] > maxVal:
                maxVal = nums[j]
        result[i] = maxVal
    
    return result

This approach is intuitive and correct. For each of the n - k + 1 windows, we perform k comparisons.

naive_sliding_window_max.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
function maxSlidingWindowNaive(nums: number[], k: number): number[] {
    const n = nums.length;
    const result: number[] = [];
    
    // For each window starting position
    for (let i = 0; i <= n - k; i++) {
        let maxVal = nums[i];
        
        // Scan all k elements in the window
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] > maxVal) {
                maxVal = nums[j];
            }
        }
        
        result.push(maxVal);
    }
    
    return result;
}
 
// Example usage
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindowNaive(nums, k)); 
// Output: [3, 3, 5, 5, 6, 7]

Complexity Analysis:

Aspect	Complexity	Explanation
Time	O(n × k)	For each of (n-k+1) windows, scan k elements
Space	O(n - k + 1)	Output array storage

Why This Fails at Scale:

Consider the worst-case scenarios for large inputs:

n = 10⁶, k = 10³: 10⁶ × 10³ = 10⁹ operations (~1 second just for comparisons)
n = 10⁶, k = 10⁵: 10⁶ × 10⁵ = 10¹¹ operations (~100 seconds)
n = 10⁶, k = 5×10⁵: 10⁶ × 5×10⁵ = 5×10¹¹ operations (~500 seconds)

For real-time systems processing millions of data points with large windows, this approach is completely impractical.

The Redundancy Problem

Attempted Optimizations That Fall Short

Optimization Attempt 1: Track the Current Maximum

•Idea: Keep track of the current maximum and update it as elements enter/leave the window.
•Adding elements: Easy! If new element > current max, update max.
•Removing elements: Problem! If the leaving element IS the maximum, what's the new maximum?
•Result: We'd need to rescan the entire window to find the new max → back to O(k) per removal.

Optimization Attempt 2: Use a Sorted Data Structure

•Idea: Maintain elements in a balanced BST or sorted set. Maximum is always accessible in O(1) or O(log k).
•Adding elements: O(log k) insertion into the balanced structure.
•Removing elements: O(log k) deletion from the balanced structure.
•Total complexity: O(n log k) — better than O(nk), but not optimal.
•Issue: Doesn't leverage the specific sliding nature of the problem.

heap_based_approach.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
// Using a max-heap with lazy deletion
// This achieves O(n log k) but not O(n)
 
import { MaxPriorityQueue } from '@datastructures-js/priority-queue';
 
function maxSlidingWindowHeap(nums: number[], k: number): number[] {
    const result: number[] = [];
    // Store [value, index] pairs in max-heap
    const maxHeap = new MaxPriorityQueue<[number, number]>({
        compare: (a, b) => b[0] - a[0] // Max by value
    });
    
    for (let i = 0; i < nums.length; i++) {
        // Add new element
        maxHeap.enqueue([nums[i], i]);
        
        // Remove elements outside window (lazy deletion)
        while (maxHeap.front()[1] <= i - k) {
            maxHeap.dequeue();
        }
        
        // Once we have k elements, record maximum
        if (i >= k - 1) {
            result.push(maxHeap.front()[0]);
        }
    }
    
    return result;
}
 
// Complexity: O(n log k) time, O(k) space
// Better than naive, but can we do better?

The O(n log k) Heap-Based Approach:

Using a max-heap with lazy deletion, we can achieve O(n log k) time:

Insert each element with its index: O(log k)
Remove stale elements (outside window) from heap top: amortized O(log k)
Query maximum: O(1)

This is a valid solution for medium-sized inputs, but for truly large inputs (n = 10⁷, k = 10⁶), the log factor becomes significant.

The Question Remains:

Can we do better than O(n log k)? Can we achieve O(n) time regardless of window size?

The answer is yes—using a technique called the monotonic deque.

The Key Insight Preview

Visualizing the Problem

Let's trace through a detailed example to build intuition for what candidates matter and which can be discarded.

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

Window-by-Window Analysis
Step	Window	Elements	Maximum	Key Observation
1	[0,2]	[1, 3, -1]	3	3 dominates 1 and -1 (later, larger)
2	[1,3]	[3, -1, -3]	3	3 still in window, still maximum
3	[2,4]	[-1, -3, 5]	5	5 enters and dominates everything
4	[3,5]	[-3, 5, 3]	5	5 still in window; 3 can't beat it
5	[4,6]	[5, 3, 6]	6	6 enters and dominates 5 and 3
6	[5,7]	[3, 6, 7]	7	7 enters and becomes new maximum

Critical Observation — The Domination Principle:

When element nums[j] enters the window, consider any earlier element nums[i] where i < j:

If nums[i] ≤ nums[j]: Element nums[i] can never be the maximum while nums[j] is in the window
Why? Because nums[j] entered later and is at least as large
When nums[i] leaves the window, nums[j] will still be there (since j > i)
Therefore, nums[i] is "dominated" and can be discarded

Example Trace:

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

i=0: See 1. Window: [1]. Candidates: [1]
i=1: See 3. 3 > 1, so 1 is dominated. Candidates: [3]
i=2: See -1. -1 < 3, keep both. Candidates: [3, -1]
     Window complete! Max = 3

i=3: See -3. -3 < -1, keep all. Candidates: [3, -1, -3]
     But wait! 3's index is 1, window starts at 1. OK.
     Max = 3

i=4: See 5. 5 > -3, 5 > -1, 5 > 3! All dominated.
     Candidates: [5]
     3's index was 1, now outside window [2,4]. Would remove anyway.
     Max = 5

i=5: See 3. 3 < 5, keep both. Candidates: [5, 3]
     Max = 5

i=6: See 6. 6 > 3, 6 > 5! Candidates: [6]
     Max = 6

i=7: See 7. 7 > 6! Candidates: [7]
     Max = 7

The Key Insight

Problem Variants and Extensions

The sliding window maximum problem has several important variants. Understanding these variants helps you recognize the pattern in different contexts and apply the same technique.

Common Problem Variants
Variant	Description	Modification Needed
Sliding Window Minimum	Find minimum instead of maximum	Use monotonically increasing deque
Variable Window Size	Window size changes over time	Track entry times, check bounds dynamically
Multiple Windows	Track max for windows of sizes k₁, k₂, ...	Use separate deques or segment trees
2D Sliding Window	Max in k×k rectangle sliding over matrix	Apply 1D technique row-wise, then column-wise
Circular Array	Array wraps around	Double the array or use modular arithmetic
Weighted Maximum	Elements have weights affecting priority	Combine with priority queue techniques

Common LeetCode Problems Using This Technique:

Problem	Difficulty	Core Technique
Sliding Window Maximum	Hard	Direct application
Longest Subarray with Abs Diff ≤ Limit	Medium	Two monotonic deques
Shortest Subarray with Sum ≥ K	Hard	Monotonic deque with prefix sums
Max Value of Equation	Hard	Monotonic deque optimization
Jump Game VI	Medium	DP with monotonic deque
Max Number of Robots	Hard	Monotonic deque + binary search

Mastering the base problem prepares you for all these variations.

The Sliding Window + Deque Pattern

Summary and What's Next

We've established a solid foundation for understanding the sliding window maximum problem. Let's consolidate what we've learned:

Key Takeaways

•Problem Definition — Given an array and window size k, find the maximum in every window of size k as it slides across the array.
•Naive Approach — O(nk) time by scanning each window independently; fails at scale for large n and k.
•Why Simple Tracking Fails — Maximum is not incrementally reducible; when the max leaves, we can't easily determine the new max.
•Heap-Based Approach — O(n log k) using a max-heap with lazy deletion; better but not optimal.
•The Domination Insight — Elements that are smaller than later elements can never become the maximum while those later elements are in the window.
•What We Need — A data structure that maintains candidates in decreasing order and supports efficient front/back operations: a monotonic deque.

What's Next:

We'll explore:

What makes a deque different from a regular queue or stack
Why a deque is essential for this problem
How to use a deque to maintain only the relevant candidates

Page Complete

1 / 4