Sliding Window Maximum Using Deque in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the deque for sliding window maximum.

DSA Python

from collections import deque

dq = [1]()

Drag options to blanks, or click blank then click option'

Alist

Bset

Cdeque

Ddict

Attempts:

3 left

💡 Hint

Common Mistakes

Using list instead of deque causes inefficient pops from the front.

Using set or dict is incorrect because they don't maintain order.

We use deque from collections to efficiently add and remove elements from both ends.

2fill in blank

medium

Complete the code to remove indices from the deque that are out of the current window.

DSA Python

if dq and dq[0] [1] i - k:
    dq.popleft()

Drag options to blanks, or click blank then click option'

A<=

B>=

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' instead of '<=' causes wrong removal.

Not removing old indices leads to incorrect maximum.

We remove the index at the front if it is outside the current window, which means its index is less than or equal to i - k.

3fill in blank

hard

Fix the error in the loop that removes smaller elements from the deque.

DSA Python

while dq and nums[dq[-1]] [1] nums[i]:
    dq.pop()

Drag options to blanks, or click blank then click option'

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' or '>' causes incorrect removals.

Using '<=' keeps smaller elements which is wrong.

We remove indices from the deque while the current number is greater than the numbers at those indices to maintain decreasing order.

4fill in blank

hard

Fill both blanks to append the maximum for each window to the result list.

DSA Python

if i [1] k - 1:
    result.[2](nums[dq[0]])

Drag options to blanks, or click blank then click option'

A>=

Bappend

C<=

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' instead of '>=' delays adding results.

Using 'pop' instead of 'append' removes elements incorrectly.

We start adding maximums to the result list once the first full window is processed (i >= k - 1). We use append to add the maximum.

5fill in blank

hard

Fill all three blanks to complete the sliding window maximum function.

DSA Python

def maxSlidingWindow(nums, k):
    from collections import deque
    dq = deque()
    result = []
    for i in range(len(nums)):
        if dq and dq[0] [1] i - k:
            dq.popleft()
        while dq and nums[dq[-1]] [2] nums[i]:
            dq.pop()
        dq.append(i)
        if i [3] k - 1:
            result.append(nums[dq[0]])
    return result

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing comparison operators causing wrong removals.

Appending results before the window is full.

The first blank removes indices out of the window (less than or equal to i - k), the second blank removes smaller elements (<), and the third blank checks if the window is full (i >= k - 1) to append the maximum.

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