Sliding Window Maximum Using Deque in DSA Python - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start with empty deque

↓

For each element in array

↓

Remove indices from back if current element is greater

↓

Add current index to back

↓

Remove front if out of window

↓

Record front element as max for current window

↓

Move to next element

↓

Repeat until end of array

We keep indexes of useful elements in a deque, removing smaller elements from the back and removing elements out of the window from the front, so the front always holds the max.

Execution Sample

DSA Python

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

This code finds the maximum in each sliding window of size k using a deque to track indices of max candidates.

Execution Table

Step	Operation	Current Index (i)	Deque Content (indices)	Deque Values	Action	Max Recorded
1	Start	-	[]	[]	Initialize empty deque	-
2	Process element	0	[0]	[1]	Add index 0	-
3	Process element	1	[1]	[3]	Pop 0 (1 < 3), add 1	-
4	Process element	2	[1,2]	[3, -1]	Add 2 (no pop)	-
5	Process element	3	[3]	[6]	Pop 2 (-1 < 6), pop 1 (3 < 6), add 3	6
6	Process element	4	[3,4]	[6, 4]	Add 4 (no pop)	6
7	Process element	5	[3,5]	[6, 5]	Pop 4 (4 < 5), add 5	6
8	Process element	6	[6]	[7]	Pop 5 (5 < 7), pop 3 (6 < 7), add 6	7
9	Process element	7	[7]	[8]	Pop 6 (7 < 8), add 7	8
10	Process element	8	[8]	[9]	Pop 7 (8 < 9), add 8	9
11	End	-	[8]	[9]	Finished processing all elements	9

💡 All elements processed, max for each window recorded.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
i	-	0	1	2	3	4	5	6	7	8	-
deque (indices)	[]	[0]	[1]	[1,2]	[3]	[3,4]	[3,5]	[6]	[7]	[8]	[8]
max recorded	[]	[]	[]	[]	[6]	[6,6]	[6,6,6]	[6,6,6,7]	[6,6,6,7,8]	[6,6,6,7,8,9]	[6,6,6,7,8,9]

Key Moments - 3 Insights

Why do we remove elements from the back of the deque when the current element is greater?

Because smaller elements behind the current one cannot be maximum in the current or future windows, so we remove them to keep only useful candidates (see steps 3, 5, 8 in execution_table).

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

The front holds the index of the maximum element for the current window. If it is out of the window (older than i - k), it must be removed to keep the window valid (as per the code condition if dq[0] <= i - k).

Why do we record the max only when i >= k - 1?

Because before that, the window is not full size yet, so we don't have a complete window maximum to record (see steps 2-4 where max is not recorded).

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the content of the deque after processing element at index 3?

A [2, 3]

B [1, 2, 3]

C [3]

D [0, 3]

💡 Hint

Check the 'Deque Content (indices)' column at step 5 in execution_table.

At which step does the first maximum get recorded in the max recorded list?

A Step 2

B Step 5

C Step 4

D Step 3

💡 Hint

Look at the 'Max Recorded' column in execution_table to see when the first value appears.

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

A Max would be recorded starting at i=1

B Max would be recorded starting at i=2

C Max would be recorded starting at i=0

D Max would be recorded starting at i=3

💡 Hint

Recall max is recorded when i >= k - 1; check variable_tracker for i values.

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 always max of current window
- Record max when window size reached
- Efficient O(n) solution for max in sliding windows

Full Transcript

This visualization shows how to find the maximum in each sliding window of size k in an array using a deque. We keep indices of useful elements in the deque. For each new element, we remove smaller elements from the back because they cannot be maximum anymore. We add the current index to the back. If the front index is out of the current window, we remove it. The front of the deque always holds the index of the maximum element for the current window. We record the maximum once the window is fully formed. The execution table traces each step, showing how the deque changes and when maximums are recorded. Key moments clarify why we remove elements and when we record maximums. The quiz tests understanding of deque content and max recording timing. This method runs efficiently in linear time.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum problem?

easy

A. To reverse the array elements

B. To sort the entire array before processing

C. To store the sum of elements in the window

D. To store indices of elements in a way that helps find the maximum efficiently

Solution

1. Step 1: Understand the role of deque

   A deque stores indices of elements in the current window, maintaining order to quickly find the max.

2. Step 2: Why not other options?

   Sorting or reversing is not done; sum is unrelated to max. Deque helps track max efficiently.

3. Final Answer:

   To store indices of elements in a way that helps find the maximum efficiently -> Option D

4. Quick Check:

   Deque stores indices for max tracking [OK]

Hint: Deque keeps max candidates in order for quick max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Assuming deque sorts the array
• Confusing deque with sum calculation

2. Which of the following is the correct syntax to initialize an empty deque in Python for the sliding window maximum problem?

easy

A. from collections import deque; dq = deque()

B. deque = []

C. dq = deque([])

D. dq = collections.deque()

Solution

1. Step 1: Import deque correctly

   Deque must be imported from collections module before use.

2. Step 2: Initialize empty deque

   Using dq = deque() after import is correct syntax; dq = deque([]) also works but less common.

3. Final Answer:

   from collections import deque; dq = deque() -> Option A

4. Quick Check:

   Import then dq = deque() [OK]

Hint: Always import deque from collections before initializing [OK]

Common Mistakes:

• Using list [] instead of deque
• Not importing deque before use
• Using collections.deque() without import

3. What is the output of the following code snippet?

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))

medium

A. [3, 3, 5, 5, 6, 7]

B. [1, 3, -1, -3, 5, 3, 6, 7]

C. [3, -1, -3, 5, 3, 6, 7]

D. [7, 6, 5, 3, -3, -1, 3, 1]

Solution

1. Step 1: Understand sliding window max logic

   For each window of size 3, the code finds max by maintaining indices in dq.

2. Step 2: Trace output for input

   Windows and max: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7

3. Final Answer:

   [3, 3, 5, 5, 6, 7] -> Option A

4. Quick Check:

   Sliding window max = [3,3,5,5,6,7] [OK]

Hint: Track max in each window by deque front index [OK]

Common Mistakes:

• Appending values instead of indices to deque
• Not removing indices out of window
• Confusing window size with output length

4. Identify the bug in this sliding window maximum code snippet:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))

medium

A. The condition to remove old indices should be dq[0] < i - k

B. The condition to remove old indices should be dq[0] <= i - k

C. The condition to remove old indices should be dq[0] == i - k + 1

D. The condition to remove old indices should be dq[0] <= i - k + 1

Solution

1. Step 1: Check condition for removing old indices

   Indices outside the window must be removed when dq[0] <= i - k (equivalent to dq[0] < i - k + 1).

2. Step 2: Analyze given condition

   Given condition dq[0] == i - k removes only if exactly equal, missing older indices or multiples; must use while loop too.

3. Final Answer:

   The condition to remove old indices should be dq[0] <= i - k -> Option B

4. Quick Check:

   Remove indices outside window with dq[0] <= i - k [OK]

Hint: Remove indices strictly less than window start index [OK]

Common Mistakes:

• Using equality instead of less than for removal
• Removing indices too late causing wrong max
• Not removing old indices at all

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size k = 4, what is the output of the sliding window maximum using deque approach?

hard

A. [4, 12, 8, 9]

B. [4, 12, 7, 9]

C. [12, 12, 12, 9]

D. [12, 12, 8, 9]

Solution

1. Step 1: Identify windows and their max values

   Windows of size 4: [4,2,12,3] max=12, [2,12,3,8] max=12, [12,3,8,7] max=12, [3,8,7,9] max=9.

2. Step 2: Verify max values carefully

   Third window max is 12, but 12 is at index 2, window covers indices 2-5: 12,3,8,7 max=12. Fourth window max is 9.

3. Final Answer:

   [12, 12, 12, 9] -> Option C

4. Quick Check:

   Sliding window max for k=4 = [12,12,12,9] [OK]

Hint: Check max in each window carefully by indices [OK]

Common Mistakes:

• Mixing up window boundaries
• Choosing wrong max by ignoring window size
• Confusing values with indices