Sliding Window Maximum - Learning Module

Loading content...

0/276

Using a Deque to Maintain Candidates

The Perfect Data Structure for the Job

In the previous page, we identified a crucial insight: we don't need to track all elements in the sliding window—only those that could potentially become the maximum. We also observed that these candidates naturally form a decreasing sequence from front to back.

Now we need a data structure that can:

Add new elements at one end (as they enter the window)
Remove elements from the same end (when new, larger elements dominate them)
Remove elements from the other end (when they exit the window)
Access the maximum (the front element) in O(1)

This dual-ended access pattern points directly to one data structure: the deque (double-ended queue). In this page, we'll see exactly why the deque is the perfect tool for maintaining our candidate pool.

What You Will Learn

By the end of this page, you will understand why a deque is essential for the sliding window maximum problem, how to use deque operations to maintain candidates efficiently, and the strategy for deciding what to store in the deque. This sets up the full monotonic deque algorithm in the next page.

Deque Recap: Double-Ended Queue Operations

Before diving into the application, let's solidify our understanding of deque operations. A deque (pronounced "deck") is a generalization of both stacks and queues, supporting insertion and deletion at both ends in O(1) time.

Core Deque Operations:

Essential Deque Operations for Sliding Window Maximum
Operation	Description	Time Complexity	Our Usage
pushBack(x)	Add element x to the back (right end)	O(1)	Add new candidate
popBack()	Remove element from the back	O(1)	Remove dominated candidates
popFront()	Remove element from the front	O(1)	Remove expired candidates
front()	View the front element	O(1)	Get current maximum
back()	View the back element	O(1)	Compare with new element
isEmpty()	Check if deque is empty	O(1)	Boundary checking

Why Not a Stack or Queue?

Let's understand why neither a stack nor a queue alone suffices:

Stack (LIFO):

✓ Can add and remove from the same end (back)
✗ Cannot efficiently remove from the front when elements exit the window
If the front element expires, we'd need to pop everything to reach it

Queue (FIFO):

✓ Can add at back and remove from front
✗ Cannot efficiently remove from the back when new larger elements arrive
We need to remove dominated elements from the back, not the front

Deque (Both):

✓ Add new elements at the back
✓ Remove dominated elements from the back
✓ Remove expired elements from the front
✓ Access maximum at the front

The deque combines the capabilities we need from both stacks and queues.

The "Both Ends" Requirement

The sliding window maximum problem requires operations at BOTH ends of our candidate list: we remove from the BACK when larger elements arrive (stack-like), and we remove from the FRONT when old elements expire (queue-like). Only a deque provides both efficiently.

What to Store in the Deque

A critical design decision is what information to store in the deque. We have two main options:

Option 1: Store Values

Pro: Simpler to implement
Con: Cannot easily check if front element has expired (exited the window)

Option 2: Store Indices

Pro: Can check expiration by comparing index with window bounds
Pro: Can retrieve values using nums[index]
Con: Slightly more indirection

For the sliding window maximum problem, storing indices is essential. Here's why:

When the window slides from position i to i+1, the element at position i exits the window. If our deque front contains index i, we know to remove it. If we only stored values, we couldn't distinguish between the same value appearing at different positions.

deque_storage_comparison.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Example: nums = [3, 3, 3], k = 2
// All values are 3, but they have different indices
 
// ❌ Storing values only - WRONG
// deque = [3, 3]  - Which 3 is which? When does each expire?
 
// ✓ Storing indices - CORRECT
// deque = [0, 1]  
// nums[0]=3, nums[1]=3
// When window moves to [1,2], we check: deque.front() = 0 < 1? Yes, remove!
// Now deque = [1, 2], correctly tracking positions
 
// The key insight: indices give us two pieces of information:
// 1. The value: nums[index]
// 2. The expiration: is index < windowStart?

Index-Based Storage Pattern

Storing indices instead of values is a common pattern in deque-based algorithms. It allows us to track both the value (via array lookup) and the position (for window boundary checks) with a single stored datum. This pattern appears in monotonic stack problems too.

The Deque Invariant:

At any point during processing, our deque will maintain these properties:

Contains only indices of elements currently in (or about to enter) the window
Decreasing order by value: nums[deque[0]] ≥ nums[deque[1]] ≥ ... ≥ nums[deque[last]]
Increasing order by index: deque[0] < deque[1] < ... < deque[last]
Front is the maximum: nums[deque[0]] is the maximum of all indexed elements

These properties are maintained by carefully managing what we add and remove.

The Candidate Addition Strategy

When a new element nums[i] enters consideration, we must decide how to update our candidate deque. The key operation is removing dominated candidates before adding the new one.

The Domination Rule:

An existing candidate at index j (where j < i) is dominated by the new element at index i if:

nums[j] ≤ nums[i]

Why? Because:

The new element is at least as large (≥)
The new element entered later, so it will stay in the window longer
Therefore, while both are in the window, nums[j] can never be the maximum
When nums[j] leaves, nums[i] will still be there

The Addition Algorithm:

candidate_addition.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
function addCandidate(deque: number[], nums: number[], i: number): void {
    // Remove all dominated candidates from the back
    // A candidate is dominated if nums[candidate] <= nums[i]
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
        deque.pop();  // Remove from back
    }
    
    // Add the new candidate
    deque.push(i);  // Add to back
}
 
// Example trace: nums = [1, 3, -1, -3, 5]
// 
// i=0: deque=[]
//      Add index 0 → deque=[0]
//      Values: [nums[0]=1]
//
// i=1: deque=[0], nums[0]=1, nums[1]=3
//      1 <= 3? Yes, pop 0 → deque=[]
//      Add index 1 → deque=[1]
//      Values: [nums[1]=3]
//
// i=2: deque=[1], nums[1]=3, nums[2]=-1
//      3 <= -1? No
//      Add index 2 → deque=[1, 2]
//      Values: [3, -1] (decreasing!)
//
// i=3: deque=[1, 2], nums[2]=-1, nums[3]=-3
//      -1 <= -3? No
//      Add index 3 → deque=[1, 2, 3]
//      Values: [3, -1, -3] (decreasing!)
//
// i=4: deque=[1, 2, 3], nums[3]=-3, nums[4]=5
//      -3 <= 5? Yes, pop 3 → deque=[1, 2]
//      -1 <= 5? Yes, pop 2 → deque=[1]
//      3 <= 5? Yes, pop 1 → deque=[]
//      Add index 4 → deque=[4]
//      Values: [nums[4]=5]

Why <= Instead of <?

We use nums[deque.back()] <= nums[i] (not strict <) because:

If an earlier element has the same value as the new element, the new element will stay in the window longer
Therefore, we prefer the newer index for equal values
This also prevents duplicate indices from accumulating

Using <= ensures we always have a strictly decreasing sequence of values (or at minimum, the rightmost occurrence of each value).

Think of it as a Stack Operation

The addition process behaves like a stack: we pop from the back until the stack top is greater than the new element, then push the new element. This is identical to building a monotonic decreasing stack! The deque just adds the ability to also pop from the front for expiration.

The Expiration Removal Strategy

As the window slides forward, elements exit from the left side. We need to remove these expired elements from our deque. This is where the front of the deque comes into play.

The Expiration Rule:

For a window starting at position windowStart (i.e., window [windowStart, windowStart + k - 1]):

An index j has expired if: j < windowStart

In other words, if j ≤ i - k where i is the current position.

The Beautiful Property:

Because our deque maintains indices in increasing order (from front to back), we only need to check the front element:

If deque.front() < windowStart, remove it
No need to check other elements—they have larger indices and are still valid
This makes expiration O(1) per removal

expiration_removal.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function removeExpired(deque: number[], windowStart: number): void {
    // Remove expired elements from the front
    // An element is expired if its index is before the window start
    while (deque.length > 0 && deque[0] < windowStart) {
        deque.shift();  // Remove from front
    }
}
 
// Example: nums = [1, 3, -1, -3, 5], k = 3
// After processing all additions, suppose deque = [1, 2, 3]
// 
// Window [0, 2]: windowStart = 0
//   deque[0] = 1 >= 0? Yes, nothing to remove
//   
// Window [1, 3]: windowStart = 1  
//   deque[0] = 1 >= 1? Yes, nothing to remove
//   
// Window [2, 4]: windowStart = 2
//   deque[0] = 1 < 2? Yes, remove 1 → deque = [2, 3]
//   deque[0] = 2 >= 2? Yes, stop
//
// Note: In practice, we do expiration check BEFORE recording the maximum
// for each window position.

Amortized O(1) Per Element

Each element enters the deque exactly once (pushed to back) and exits at most once (either popped from back when dominated, or popped from front when expired). Since each element participates in at most 2 operations across the entire algorithm, the total work for all n elements is O(n), giving O(1) amortized per element.

Combining the Operations

Now let's see how the addition and expiration operations work together as we process the array. The order of operations for each element i is:

Remove dominated candidates — Pop from back while nums[back] <= nums[i]
Add new candidate — Push i to the back
Remove expired candidates — Pop from front while front < i - k + 1
Record maximum — The front of the deque is the maximum for this window (if window is complete)

combined_operations.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
function processElement(
    deque: number[], 
    nums: number[], 
    i: number, 
    k: number,
    result: number[]
): void {
    // Step 1 & 2: Remove dominated, then add new candidate
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
        deque.pop();
    }
    deque.push(i);
    
    // Step 3: Remove expired candidates
    const windowStart = i - k + 1;
    while (deque.length > 0 && deque[0] < windowStart) {
        deque.shift();
    }
    
    // Step 4: Record maximum (if we've filled the first window)
    if (i >= k - 1) {
        result.push(nums[deque[0]]);
    }
}
 
// Full algorithm
function maxSlidingWindow(nums: number[], k: number): number[] {
    const deque: number[] = [];
    const result: number[] = [];
    
    for (let i = 0; i < nums.length; i++) {
        processElement(deque, nums, i, k, result);
    }
    
    return result;
}

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

Step-by-Step Deque Operations
i	nums[i]	After Remove Dominated	After Add	After Remove Expired	Window	Max
0	1	[]	[0]	[0]	incomplete
1	3	[]	[1]	[1]	incomplete
2	-1	[1]	[1, 2]	[1, 2]	[0,2]	3
3	-3	[1, 2]	[1, 2, 3]	[1, 2, 3]	[1,3]	3
4	5	[]	[4]	[4]	[2,4]	5
5	3	[4]	[4, 5]	[4, 5]	[3,5]	5
6	6	[]	[6]	[6]	[4,6]	6
7	7	[]	[7]	[7]	[5,7]	7

The Decreasing Property Maintained

Notice how after every operation, the values in the deque (nums[deque[i]]) form a decreasing sequence. This is the monotonic property that makes the front always hold the maximum!

Visualizing Deque State Transitions

Let's visualize the deque as a horizontal container where the front is on the left and the back is on the right. Values are written below indices for clarity.

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

════════════════════════════════════════════════════════════════
i=0: See 1
     Deque: [0]
             1
     Window: [1, _, _] - incomplete

════════════════════════════════════════════════════════════════
i=1: See 3 (3 > 1, so 1 is dominated)
     Pop 0, then push 1
     Deque: [1]
             3
     Window: [1, 3, _] - incomplete

════════════════════════════════════════════════════════════════
i=2: See -1 (-1 < 3, keep both)
     Push 2
     Deque: [1, 2]
             3  -1
     Window: [1, 3, -1] - complete! Max = nums[1] = 3

════════════════════════════════════════════════════════════════
i=3: See -3 (-3 < -1, keep all)
     Push 3
     Deque: [1, 2, 3]
             3  -1 -3
     Check expiration: index 1 >= windowStart 1? Yes, OK
     Window: [3, -1, -3] - Max = nums[1] = 3

════════════════════════════════════════════════════════════════
i=4: See 5 (5 > all!)
     Pop 3 (since -3 <= 5)
     Pop 2 (since -1 <= 5)  
     Pop 1 (since 3 <= 5)
     Push 4
     Deque: [4]
             5
     Check expiration: index 4 >= windowStart 2? Yes, OK
     Window: [-1, -3, 5] - Max = nums[4] = 5

════════════════════════════════════════════════════════════════
i=5: See 3 (3 < 5, keep both)
     Push 5
     Deque: [4, 5]
             5  3
     Check expiration: index 4 >= windowStart 3? Yes, OK
     Window: [-3, 5, 3] - Max = nums[4] = 5

════════════════════════════════════════════════════════════════
i=6: See 6 (6 > 3, 6 > 5)
     Pop 5 (since 3 <= 6)
     Pop 4 (since 5 <= 6)
     Push 6
     Deque: [6]
             6
     Check expiration: index 6 >= windowStart 4? Yes, OK
     Window: [5, 3, 6] - Max = nums[6] = 6

════════════════════════════════════════════════════════════════
i=7: See 7 (7 > 6)
     Pop 6 (since 6 <= 7)
     Push 7
     Deque: [7]
             7
     Check expiration: index 7 >= windowStart 5? Yes, OK
     Window: [3, 6, 7] - Max = nums[7] = 7

Key Observations

Notice three critical patterns: (1) The deque always maintains decreasing order of values, (2) When a large element arrives, it 'clears out' smaller elements, (3) The front (leftmost) element is always the answer for the current window.

Language-Specific Deque Implementations

Different programming languages provide different deque implementations. Here's how to use deques effectively in common languages:

python_deque.py
Python
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
from collections import deque
 
# Python's collections.deque is a doubly-linked list
# providing O(1) operations at both ends
 
dq = deque()
 
# Add to back (right)
dq.append(1)       # deque([1])
dq.append(2)       # deque([1, 2])
 
# Add to front (left)
dq.appendleft(0)   # deque([0, 1, 2])
 
# Remove from back
dq.pop()           # returns 2, deque([0, 1])
 
# Remove from front  
dq.popleft()       # returns 0, deque([1])
 
# Access front and back
front = dq[0]      # First element
back = dq[-1]      # Last element
 
# Check if empty
if dq:             # Truthy if not empty
    print("Not empty")
 
# For sliding window maximum:
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()  # Will store indices
    result = []
    
    for i, num in enumerate(nums):
        # Remove dominated from back
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        
        # Remove expired from front
        while dq[0] <= i - k:
            dq.popleft()
        
        # Record result after first window
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

JavaScript Array Caveat

In JavaScript, Array.shift() is O(n) because it re-indexes all elements. For sliding window problems with large inputs, this can cause Time Limit Exceeded. Use a proper circular buffer Deque implementation or accept the performance hit for smaller inputs.

Summary and What's Next

We've explored how to use a deque as the foundation for solving the sliding window maximum problem. Let's consolidate the key points:

Key Takeaways

•Deque is essential — We need O(1) operations at both ends: add/remove at back for domination, remove at front for expiration.
•Store indices, not values — Indices allow us to both retrieve values (via array lookup) and check expiration (by comparing to window bounds).
•Addition removes dominated elements — Before adding index i, pop all indices j where nums[j] ≤ nums[i] from the back.
•Expiration removes old elements — Pop indices from the front that are no longer within the window bounds.
•The front is always the maximum — The invariant of decreasing values ensures the front element is the answer.
•Use language-specific deques — Python's collections.deque, Java's ArrayDeque, and C++'s std::deque all provide O(1) operations.

What's Next:

Now that we understand how to use a deque for candidate management, we're ready to formalize the monotonic deque technique. In the next page, we'll:

Define what makes a deque "monotonic"
Present the complete algorithm with all edge cases handled
Prove the correctness of the approach
Analyze why this achieves O(n) time complexity

The monotonic deque is more than a solution to this problem—it's a powerful technique applicable to many optimization problems.

Page Complete

You now understand how to use a deque to maintain candidate maximum values: store indices, remove dominated candidates from the back, remove expired candidates from the front, and read the maximum from the front. Next, we'll formalize this into the monotonic deque technique.