Sliding Window Maximum Using Deque in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

A deque helps keep track of indices of elements in the current window in a way that the front always holds the index of the maximum element. It allows efficient insertion and removal from both ends to maintain the window's maximum.

intermediate

In the Sliding Window Maximum problem, why do we remove elements from the back of the deque when they are smaller than the current element?

Because smaller elements cannot be the maximum if a bigger element comes after them in the window. Removing them keeps the deque elements in decreasing order, ensuring the front is always the maximum.

beginner

What does the deque store in the Sliding Window Maximum algorithm?

The deque stores indices of elements from the array, not the elements themselves. This helps to check if an element is out of the current window and to access the element values easily.

intermediate

How do you know when to remove the front element of the deque in the Sliding Window Maximum problem?

Remove the front element if its index is outside the current window (i.e., if it is less than the current index minus window size plus one). This keeps the deque relevant to the current window.

intermediate

What is the time complexity of the Sliding Window Maximum algorithm using a deque?

The time complexity is O(n) because each element is added and removed from the deque at most once, making the operations linear in total.

What does the front of the deque represent in the Sliding Window Maximum algorithm?

A The size of the current window

B Index of the minimum element in the current window

C The last element added to the window

D Index of the maximum element in the current window

The front of the deque always holds the index of the maximum element in the current sliding window.

Why do we remove elements from the back of the deque when processing a new element?

A Because they are out of the window

B Because they are smaller than the new element

C Because they are equal to the new element

D Because the deque is full

Smaller elements at the back are removed to maintain decreasing order and ensure the maximum is at the front.

What data structure is best suited for the Sliding Window Maximum problem?

A Deque

B Stack

C Queue

D Hash Map

A deque allows efficient insertion and removal from both ends, which is essential for this problem.

How many times can each element be added and removed from the deque in the Sliding Window Maximum algorithm?

A Multiple times

B Once

C Twice

D Never removed

Each element can be added once and removed once, leading to O(n) complexity.

What happens if the front element of the deque is outside the current window?

A It is removed from the front

B The window size increases

C It is moved to the back

D It stays in the deque

Elements outside the window are removed from the front to keep the deque relevant.

Explain how a deque helps solve the Sliding Window Maximum problem efficiently.

Think about how the deque keeps track of maximums as the window slides.

Describe the step-by-step process of updating the deque when moving the sliding window by one position.

Focus on what happens to the deque before and after adding the new element.

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