Sliding Window Maximum Using Deque in DSA Rust

Mental Model

Keep track of the biggest numbers in the current window using a special list that quickly removes smaller numbers.

Analogy: Imagine you are watching runners in a race and only remember the fastest ones ahead, forgetting slower runners behind you as you move forward.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size = 4
Deque stores indexes of elements in decreasing order of their values
Example:
Deque: [6, 7, 8, 9]  (indexes of 8, 9, 10, 12)
Window covers elements: 8, 9, 10, 12
Maximum is at front: 12

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size = 4

Goal: Find the maximum number in every window of size 4 as it slides from left to right

Step 1: Start with empty deque, process first element 2 at index 0

Deque: [0] (stores index of 2)
Window: [2]

Why: Add first element index to deque as starting point

Step 2: Process element 1 at index 1, 1 is smaller than 2, so add index 1 to deque

Deque: [0, 1]
Window: [2, 1]

Why: Keep indexes of elements in decreasing order, 1 is smaller so stays behind 2

Step 3: Process element 3 at index 2, remove indexes with smaller values (1) from back, then add index 2

Deque: [0, 2]
Window: [2, 1, 3]

Why: 3 is bigger, so remove smaller elements behind to keep max at front

Step 4: Process element 4 at index 3, remove index 2 (3) from back, add index 3

Deque: [0, 3]
Window: [2, 1, 3, 4]

Why: 4 is bigger, so remove smaller elements behind to keep max at front

Step 5: Slide window forward, remove index 0 (2) if out of window, process element 6 at index 4, remove index 3 (4), add index 4

Deque: [4]
Window: [1, 3, 4, 6]

Why: Remove elements out of window and smaller than new element to keep max at front

Step 6: Process element 3 at index 5, add index 5 since 3 is smaller than 6

Deque: [4, 5]
Window: [3, 4, 6, 3]

Why: Keep smaller elements behind max to maintain order

Step 7: Process element 8 at index 6, remove indexes 5 (3) and 4 (6) from back, add index 6

Deque: [6]
Window: [4, 6, 3, 8]

Why: 8 is bigger, so remove smaller elements behind

Step 8: Process element 9 at index 7, remove index 6 (8), add index 7

Deque: [7]
Window: [6, 3, 8, 9]

Why: 9 is bigger, so remove smaller elements behind

Result:

Final maximums for each window: [4, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn sliding_window_maximum(nums: &[i32], k: usize) -> Vec<i32> {
    let mut result = Vec::new();
    let mut deque: VecDeque<usize> = VecDeque::new();

    for i in 0..nums.len() {
        // Remove indexes out of current window
        while let Some(&front) = deque.front() {
            if front + k <= i {
                deque.pop_front();
            } else {
                break;
            }
        }

        // Remove smaller elements from back
        while let Some(&back) = deque.back() {
            if nums[back] < nums[i] {
                deque.pop_back();
            } else {
                break;
            }
        }

        deque.push_back(i);

        // Start adding max to result when first window is complete
        if i + 1 >= k {
            if let Some(&front) = deque.front() {
                result.push(nums[front]);
            }
        }
    }

    result
}

fn main() {
    let nums = vec![2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56];
    let k = 4;
    let max_values = sliding_window_maximum(&nums, k);
    for val in max_values {
        print!("{} ", val);
    }
    println!();
}

while let Some(&front) = deque.front() { if front + k <= i { deque.pop_front(); } else { break; } }

Remove indexes that are out of the current sliding window range

while let Some(&back) = deque.back() { if nums[back] < nums[i] { deque.pop_back(); } else { break; } }

Remove smaller elements from the back to keep deque decreasing

deque.push_back(i);

Add current element index to deque

if i + 1 >= k { if let Some(&front) = deque.front() { result.push(nums[front]); } }

Add the maximum element for the current window to the result

Output

4 6 6 8 9 10 12 56 

Complexity Analysis

Time: O(n) because each element is added and removed from the deque at most once

Space: O(k) because the deque stores indexes of elements within the current window

vs Alternative: Naive approach is O(n*k) by scanning each window fully; deque approach is much faster with O(n)

Edge Cases

Empty array

Returns empty result without error

DSA Rust

for i in 0..nums.len() {

Window size larger than array length

No windows formed, returns empty result

DSA Rust

if i + 1 >= k {

All elements equal

Deque keeps only one index, maximum is that value repeated

DSA Rust

while let Some(&back) = deque.back() { if nums[back] < nums[i] { deque.pop_back(); } else { break; } }

When to Use This Pattern

When asked to find maximum or minimum in every sliding window efficiently, use the deque pattern to maintain candidates in order and achieve O(n) time.

Common Mistakes

Mistake: Not removing indexes that are out of the current window from the front of the deque
Fix: Add a check to pop from front when the index is outside the window range

Mistake: Not removing smaller elements from the back before adding new element index
Fix: Pop from back all indexes whose values are smaller than the current element

Summary

Finds the maximum value in every sliding window of size k in an array efficiently.

Use when you need fast maximum queries over moving windows without recomputing each time.

Keep indexes of elements in a deque in decreasing order, removing outdated or smaller elements as you slide.

Practice

1. For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k=3, what is the maximum of the first window [1,3,-1]?

easy

A. 1

B. -1

C. 3

D. 5

Solution

1. Step 1: First window

   Window [1, 3, -1] contains elements at indices 0, 1, 2.

2. Step 2: Maximum

   max(1, 3, -1) = 3.

3. Step 3: Deque state

   After processing first window: deque = [1] (index of 3, since 3 is largest and -1 is removed because 3 > -1 and 3 came before -1).

4. Final Answer:

   3 -> Option C

5. Quick Check:

   max(1,3,-1)=3. [OK]

Hint: max(1,3,-1)=3. Deque front holds index 1 (value 3) after processing window. [OK]

Common Mistakes:

• Returning the last element -1
• Returning the first element 1
• Not recognizing 3 as the maximum

2. In the sliding window maximum problem, what does the deque store?

medium

A. The maximum values seen so far

B. Indices of elements in decreasing order of their values

C. All elements in the current window

D. The sum of the current window

Solution

1. Step 1: Deque content

   The deque stores INDICES (not values), arranged so that nums[deque.front()] is always the maximum of the current window.

2. Step 2: Decreasing order

   Elements are kept in decreasing order of their values - smaller elements behind a larger one are useless (they can never be the maximum while the larger element is in the window).

3. Final Answer:

   Indices of elements in decreasing value order. -> Option B

4. Quick Check:

   Deque = indices in decreasing value order. Front = current window max. [OK]

Hint: Deque stores indices, decreasing by value. Front index = current max. [OK]

Common Mistakes:

• Thinking deque stores values not indices
• Thinking all window elements are stored
• Confusing with a max-heap approach

3. What is the time complexity of sliding window maximum using a monotonic deque?

medium

A. O(n²)

B. O(n log n)

C. O(n)

D. O(n × k)

Solution

1. Step 1: Each element pushed once

   Each element is pushed to the deque exactly once.

2. Step 2: Each element popped at most once

   Each element is popped from either front or back at most once. Total push+pop operations: 2n = O(n).

3. Step 3: Overall

   n iterations × O(1) amortized per iteration = O(n).

4. Final Answer:

   O(n) - each element pushed and popped at most once. -> Option C

5. Quick Check:

   Each element: 1 push + at most 1 pop = O(n) total. [OK]

Hint: Monotonic deque: each element pushed once, popped once = O(n). Better than O(n×k) naive. [OK]

Common Mistakes:

• Saying O(n×k) by not accounting for amortized analysis
• Saying O(n log n) confusing with heap-based approach
• Not knowing each element is pushed/popped at most once total

4. When processing a new element i in sliding window maximum, when do we pop from the BACK of the deque?

hard

A. When deque.back() index is outside the window

B. When nums[deque.back()] <= nums[i] - smaller elements are useless

C. When the deque is full (size == k)

D. When nums[i] is negative

Solution

1. Step 1: Why pop from back

   If nums[deque.back()] <= nums[i], the back element can never be the window maximum while nums[i] is in the window. nums[i] is larger AND will leave the window later.

2. Step 2: Keep decreasing order

   Pop all elements from back where nums[back] <= nums[i], then push i. This maintains the monotonic decreasing invariant.

3. Final Answer:

   Pop back when nums[deque.back()] <= nums[i]. -> Option B

4. Quick Check:

   Back pop: current element >= back element → back is useless, remove it. [OK]

Hint: Pop back when nums[back] <= nums[current]. Larger current makes smaller back useless forever. [OK]

Common Mistakes:

• Confusing front pop (out-of-window check) with back pop (useless element removal)
• Popping only when strictly less than, missing equals case
• Thinking deque size triggers back pop

5. When processing a new element i in sliding window maximum, when do we pop from the FRONT of the deque?

hard

A. When nums[deque.front()] < nums[i]

B. When deque.front() <= i - k (front index is outside the current window)

C. When the deque has more than k elements

D. When nums[i] is the new maximum

Solution

1. Step 1: Window boundary

   The current window is [i-k+1, i]. The front of deque holds the maximum's index. If that index <= i-k, it's outside the window.

2. Step 2: Pop expired maximum

   Pop front when deque.front() <= i - k. The front is no longer in the current window - the next front becomes the new maximum.

3. Final Answer:

   Pop front when front index <= i - k (out of window). -> Option B

4. Quick Check:

   Front pop: index out of window (front <= i-k). Back pop: value useless (back <= current). [OK]

Hint: Front pop = expired (index out of window). Back pop = useless (value smaller than current). [OK]

Common Mistakes:

• Confusing front pop condition with back pop condition
• Using < i-k instead of <= i-k (off by one)
• Thinking front pop is based on value comparison