Sliding Window Maximum Using Deque in DSA Rust - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start with empty deque

↓

For each element in array

↓

Remove indices from deque back if their values < current element

↓

Add current index to deque back

↓

Remove front index if it is out of current window

↓

If window is fully formed, record value at deque front as max

↓

Repeat until end of array

↓

Return list of max values

We keep indexes of useful elements in a deque, removing smaller elements from the back and outdated elements from the front, to find max in each sliding window.

Execution Sample

DSA Rust

fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    let mut deq = Vec::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        while !deq.is_empty() && nums[*deq.last().unwrap()] < nums[i] {
            deq.pop();
        }
        deq.push(i);
        if deq[0] + k <= i {
            deq.remove(0);
        }
        if i + 1 >= k {
            result.push(nums[deq[0]]);
        }
    }
    result
}

This Rust function finds the maximum in each sliding window of size k using a deque to track indices of potential max elements.

Execution Table

Step	Operation	Deque Indices	Deque Values	Window Indices	Max Recorded	Visual State
1	Add index 0 (value 1)	[0]	[1]	[0]	—	Deque: [0(1)] Window: [0] Max: —
2	Add index 1 (value 3), pop 0 since 1 < 3	[1]	[3]	[0,1]	—	Deque: [1(3)] Window: [0,1] Max: —
3	Add index 2 (value -1), no pop	[1,2]	[3,-1]	[0,1,2]	3	Deque: [1(3),2(-1)] Window: [0,1,2] Max: 3
4	Add index 3 (value -3), no pop	[1,2,3]	[3,-1,-3]	[1,2,3]	3	Deque: [1(3),2(-1),3(-3)] Window: [1,2,3] Max: 3
5	Add index 4 (value 5), pop 3,2,1 since all < 5	[4]	[5]	[2,3,4]	5	Deque: [4(5)] Window: [2,3,4] Max: 5
6	Add index 5 (value 3), no pop	[4,5]	[5,3]	[3,4,5]	5	Deque: [4(5),5(3)] Window: [3,4,5] Max: 5
7	Add index 6 (value 6), pop 5,4 since < 6	[6]	[6]	[4,5,6]	6	Deque: [6(6)] Window: [4,5,6] Max: 6
8	Add index 7 (value 7), pop 6 since < 7	[7]	[7]	[5,6,7]	7	Deque: [7(7)] Window: [5,6,7] Max: 7
9	End of array reached	[7]	[7]	[5,6,7]	7	Final max list: [3,3,5,5,6,7]

💡 All elements processed, max values recorded for each full window.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
deque	[]	[0]	[1]	[1,2]	[1,2,3]	[4]	[4,5]	[6]	[7]	[7]
result	[]	[]	[]	[3]	[3,3]	[3,3,5]	[3,3,5,5]	[3,3,5,5,6]	[3,3,5,5,6,7]	[3,3,5,5,6,7]
i (index)	0	0	1	2	3	4	5	6	7	7

Key Moments - 3 Insights

Why do we remove indices from the back of the deque when their values are less than the current element?

Because those smaller elements cannot be the maximum in the current or future windows, removing them keeps the deque holding only candidates for max (see execution_table steps 2, 5, 7, 8).

Why do we remove the front index if it is out of the current window?

The front index represents the oldest element; if it is outside the current window, it cannot be max anymore, so we remove it to keep the deque valid (see execution_table step 5 where window moves forward).

How do we know when to record the max value from the deque?

We record max only after the first full window is formed, i.e., when i + 1 >= k, taking the value at the front of the deque as max (see execution_table steps 3 and onwards).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the deque indices and why?

A [1,2,3]

B [4]

C [3,4]

D [2,3,4]

💡 Hint

Check step 5 where smaller values are popped before adding index 4.

At which step does the first max value get recorded in the result?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for when result first gets a value in the execution_table.

If the window size k was 4 instead of 3, how would the max recording step change?

A Max recorded starting at step 4

B Max recorded starting at step 2

C Max recorded starting at step 3

D Max recorded starting at step 5

💡 Hint

Max recording starts when i + 1 >= k, so check variable i in variable_tracker.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of elements
- Remove smaller elements from back before adding new
- Remove front if out of window
- Front of deque is max for current window
- Record max after first full window
- Efficient O(n) solution for max in sliding windows

Full Transcript

This visualization shows how to find the maximum value in each sliding window of size k in an array using a deque. We keep indices of elements in the deque, removing smaller elements from the back to maintain candidates for maximum. We also remove the front index if it falls outside the current window. After the first full window is formed, we record the value at the front of the deque as the maximum for that window. The execution table traces each step, showing how the deque changes, when elements are popped, and when max values are recorded. The variable tracker shows the state of the deque and result list after each step. Key moments clarify why we remove elements and when we record max values. The quiz tests understanding of these steps. This method runs efficiently in linear time.

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