Sliding Window Maximum Using Deque in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

What is the output of the following Python code that finds the maximum in each sliding window of size 3 using a deque?

DSA Python

from collections import deque

def sliding_window_max(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(sliding_window_max([1,3,-1,-3,5,3,6,7], 3))

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

B [1, 3, -1, -3, 5, 3]

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

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

💡 Hint

Remember the deque stores indices of elements in decreasing order of their values.

The code maintains a deque of indices where the values are in decreasing order. For each window, the front of the deque is the index of the maximum element. The output is the list of these maximums for each sliding window.

🧠 Conceptual

intermediate

Why Use a Deque for Sliding Window Maximum?

Why is a deque the best data structure to find the maximum in a sliding window efficiently?

A Because it uses hashing to find the maximum element instantly.

B Because it sorts the elements automatically, so the maximum is always at the front.

C Because it stores elements in a tree structure for quick maximum lookup.

D Because it allows adding and removing elements from both ends in O(1) time, maintaining candidates for maximum efficiently.

💡 Hint

Think about how the sliding window moves and how elements enter and leave the window.

A deque supports adding and removing elements from both ends in constant time. This allows us to keep only useful elements (potential maximums) in the deque and discard others efficiently as the window slides.

🔧 Debug

advanced

Identify the Error in Sliding Window Maximum Implementation

What error does the following code produce when run, and why? from collections import deque def sliding_window_max(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 i >= k - 1: if dq[0] <= i - k: dq.popleft() result.append(nums[dq[0]]) return result print(sliding_window_max([1,3,-1,-3,5,3,6,7], 3))

A IndexError because dq[0] is accessed before checking if dq is empty.

B TypeError because nums[dq[-1]] is compared with nums[i] incorrectly.

C Wrong output because the window removal condition is checked after appending the max.

D No error, outputs correct maximums.

💡 Hint

Check the order of removing indices outside the window and appending the maximum.

The code appends the maximum before removing indices that are out of the current window, causing the maximum to sometimes be from an old window. The removal of indices outside the window should happen before appending the maximum.

❓ Predict Output

advanced

Output of Sliding Window Maximum with Window Size 1

What is the output of this code when the window size is 1?

DSA Python

from collections import deque

def sliding_window_max(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(sliding_window_max([4, 2, 12, 3, 8], 1))

A [12]

B [4, 2, 12, 3, 8]

C [4]

D []

💡 Hint

When the window size is 1, each element is its own window.

With window size 1, the maximum in each window is the element itself, so the output is the original list.

🧠 Conceptual

expert

Time Complexity of Sliding Window Maximum Using Deque

What is the time complexity of finding the sliding window maximum using a deque for an array of length n and window size k, and why?

A O(n) because each element is added and removed from the deque at most once.

B O(n*k) because for each element, we scan k elements in the window.

C O(k*log n) because the deque maintains a sorted order using binary search.

D O(n^2) because nested loops are used to find maximums.

💡 Hint

Consider how many times each element can be pushed or popped from the deque.

Each element is pushed into the deque once and popped at most once, so the total operations are proportional to n, making the algorithm O(n).

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