Sliding Window Maximum Using Deque in DSA Python

Mental Model

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

Analogy: Imagine a line of people waiting to enter a ride, but only the tallest people stay in line because shorter ones get blocked and leave. The tallest person at the front is always the leader of the group.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size = 4
Deque stores indices of elements in decreasing order of values
Example:
Deque: [6, 7, 8, 9]  (indices of values 8, 9, 10, 12)
Window covers elements: 8, 9, 10, 12
Max 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 value 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] (values: [2])

Why: Add first element index to deque as starting point

Step 2: Process second element (1 at index 1), remove smaller from back

Deque: [0, 1] (values: [2, 1])

Why: 1 is smaller than 2, so keep both; 2 stays in front

Step 3: Process third element (3 at index 2), remove smaller from back

Deque: [2] (values: [3])

Why: 3 is bigger than 1 and 2, so remove them; 3 becomes new max candidate

Step 4: Process fourth element (4 at index 3), remove smaller from back

Deque: [3] (values: [4])

Why: 4 is bigger than 3, remove 3; 4 is new max candidate

Step 5: Window is full, record max (value at front index 3 = 4)

Max for window [2,1,3,4] is 4

Why: Front of deque always holds max for current window

Step 6: Slide window, process fifth element (6 at index 4), remove smaller from back

Deque: [4] (values: [6])

Why: 6 is bigger than 4, remove 4; 6 is new max candidate

Step 7: Record max for window [1,3,4,6] from front index 4 = 6

Max is 6

Why: Deque front is max for current window

Step 8: Process sixth element (3 at index 5), add to deque

Deque: [4, 5] (values: [6, 3])

Why: 3 is smaller than 6, keep both

Step 9: Process seventh element (8 at index 6), remove smaller from back

Deque: [6] (values: [8])

Why: 8 is bigger than 3 and 6, remove them; 8 is new max candidate

Step 10: Record max for window [4,6,3,8] from front index 6 = 8

Max is 8

Why: Deque front is max for current window

Step 11: Process eighth element (9 at index 7), remove smaller from back

Deque: [7] (values: [9])

Why: 9 is bigger than 8, remove 8; 9 is new max candidate

Step 12: Record max for window [6,3,8,9] from front index 7 = 9

Max is 9

Why: Deque front is max for current window

Step 13: Process ninth element (10 at index 8), remove smaller from back

Deque: [8] (values: [10])

Why: 10 is bigger than 9, remove 9; 10 is new max candidate

Step 14: Record max for window [3,8,9,10] from front index 8 = 10

Max is 10

Why: Deque front is max for current window

Step 15: Process tenth element (12 at index 9), remove smaller from back

Deque: [9] (values: [12])

Why: 12 is bigger than 10, remove 10; 12 is new max candidate

Step 16: Record max for window [8,9,10,12] from front index 9 = 12

Max is 12

Why: Deque front is max for current window

Step 17: Process eleventh element (56 at index 10), remove smaller from back

Deque: [10] (values: [56])

Why: 56 is bigger than 12, remove 12; 56 is new max candidate

Step 18: Record max for window [9,10,12,56] from front index 10 = 56

Max is 56

Why: Deque front is max for current window

Result:

Max values for each window: [4, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA Python

from collections import deque

class SlidingWindowMax:
    def max_sliding_window(self, nums, k):
        if not nums or k == 0:
            return []
        dq = deque()  # stores indices
        result = []
        for i in range(len(nums)):
            # Remove indices out of current window
            while dq and dq[0] < i - k + 1:
                dq.popleft()  # remove from front
            # Remove smaller values from back
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()  # remove from back
            dq.append(i)  # add current index
            # Append max to result when first window is ready
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

if __name__ == '__main__':
    arr = [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
    window_size = 4
    solver = SlidingWindowMax()
    output = solver.max_sliding_window(arr, window_size)
    print(output)

while dq and dq[0] < i - k + 1:

Remove indices that are out of the current window from the front

while dq and nums[dq[-1]] < nums[i]:

Remove smaller values from the back to keep deque decreasing

dq.append(i)

Add current index to deque as a candidate for max

if i >= k - 1:

Start recording max values once the first full window is processed

result.append(nums[dq[0]])

Add the value at the front of deque as max for current window

Output

[4, 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 indices only for the current window size

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

Edge Cases

Empty array

Returns empty list immediately

DSA Python

if not nums or k == 0:
            return []

Window size larger than array length

Returns max of entire array as single window

DSA Python

while dq and dq[0] < i - k + 1:

All elements equal

Deque keeps indices in order; max is the same for all windows

DSA Python

while dq and nums[dq[-1]] < nums[i]:

When to Use This Pattern

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

Common Mistakes

Mistake: Not removing indices that are out of the current window from the front
Fix: Add a check to pop from front when indices fall outside the window range

Mistake: Not removing smaller elements from the back, causing incorrect max values
Fix: Pop from back all indices whose values are smaller than current element before adding new index

Summary

Finds the maximum value in every sliding window of size k using a deque.

Use when you need fast max queries over moving windows in an array.

Keep indices of elements in a deque in decreasing order to quickly find max.

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