Sliding Window Maximum (Monotonic Deque)

▶

Steps

setup

Initialize variables

Initialize an empty deque to store indices and an empty result list to store maximums.

💡 Setting up the deque and result list is essential before processing any elements.

Line:

dq = deque()  # stores indices
result = []

💡 The deque will hold indices, not values, to efficiently track window boundaries.

traverse

Process element at index 0 (value 1)

Start processing the first element (1). The deque is empty, so we push index 0.

💡 The first element always gets added since the deque is empty.

Line:

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

💡 Deque now contains index 0, representing the value 1.

traverse

Process element at index 1 (value 3)

Compare current value 3 with value at deque's back (index 0 → 1). Since 3 > 1, pop index 0 and push index 1.

💡 We remove smaller elements from the back to maintain decreasing order.

Line:

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

💡 Deque now holds index 1 only, representing the larger value 3.

traverse

Process element at index 2 (value -1)

Current value -1 is less than value at deque's back (index 1 → 3), so no pops. Push index 2.

💡 We only pop smaller elements; since -1 < 3, we keep both indices.

Line:

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

💡 Deque now holds indices [1, 2], values [3, -1].

insert

Window full at index 2, append max to result

Window size reached k=3. Append value at front of deque (index 1 → 3) to result.

💡 The front of the deque always holds the max for the current window.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3].

traverse

Process element at index 3 (value -3)

Current value -3 is less than value at deque's back (index 2 → -1), so no pops. Push index 3.

💡 We maintain the decreasing order by only popping smaller elements.

Line:

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

💡 Deque now holds indices [1, 2, 3], values [3, -1, -3].

shrink

Remove front index if out of window

Check if front index (1) is out of window (i-k=0). Since 1 > 0, no removal.

💡 We remove indices from front if they fall outside the current window.

Line:

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

💡 Deque remains [1, 2, 3].

insert

Window full at index 3, append max to result

Window size is k=3. Append value at front of deque (index 1 → 3) to result.

💡 The maximum for this window is at the front of the deque.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3, 3].

traverse

Process element at index 4 (value 5)

Current value 5 is greater than values at back (index 3 → -3, index 2 → -1, index 1 → 3). Pop all smaller indices and push index 4.

💡 We remove all smaller elements from the back to maintain decreasing order.

Line:

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

💡 Deque now holds only index 4, value 5.

shrink

Remove front index if out of window

Check if front index (4) is out of window (i-k=1). Since 4 > 1, no removal.

💡 We ensure the front index is within the current window.

Line:

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

💡 Deque remains [4].

insert

Window full at index 4, append max to result

Window size is k=3. Append value at front of deque (index 4 → 5) to result.

💡 The maximum for this window is at the front of the deque.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3, 3, 5].

traverse

Process element at index 5 (value 3)

Current value 3 is less than value at back (index 4 → 5), so push index 5 without popping.

💡 We only pop smaller elements; 3 < 5 so no pops.

Line:

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

💡 Deque now holds [4, 5], values [5, 3].

shrink

Remove front index if out of window

Check if front index (4) is out of window (i-k=2). Since 4 > 2, no removal.

💡 Front index must be inside the window.

Line:

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

💡 Deque remains [4, 5].

insert

Window full at index 5, append max to result

Window size is k=3. Append value at front of deque (index 4 → 5) to result.

💡 Maximum is always at the front of the deque.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3, 3, 5, 5].

traverse

Process element at index 6 (value 6)

Current value 6 is greater than values at back (index 5 → 3, index 4 → 5). Pop indices 5 and 4, then push index 6.

💡 Pop smaller elements to maintain decreasing order.

Line:

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

💡 Deque now holds [6], value 6.

shrink

Remove front index if out of window

Check if front index (6) is out of window (i-k=3). Since 6 > 3, no removal.

💡 Ensure front index is inside window.

Line:

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

💡 Deque remains [6].

insert

Window full at index 6, append max to result

Window size is k=3. Append value at front of deque (index 6 → 6) to result.

💡 Maximum is at the front of the deque.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3, 3, 5, 5, 6].

traverse

Process element at index 7 (value 7)

Current value 7 is greater than value at back (index 6 → 6). Pop index 6 and push index 7.

💡 Pop smaller elements to maintain decreasing order.

Line:

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

💡 Deque now holds [7], value 7.

shrink

Remove front index if out of window

Check if front index (7) is out of window (i-k=4). Since 7 > 4, no removal.

💡 Ensure front index is inside window.

Line:

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

💡 Deque remains [7].

insert

Window full at index 7, append max to result

Window size is k=3. Append value at front of deque (index 7 → 7) to result.

💡 Maximum is at the front of the deque.

Line:

if i >= k - 1:
    result.append(nums[dq[0]])

💡 Result now contains [3, 3, 5, 5, 6, 7].

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()  # stores indices
    result = []
    for i in range(n):
        # STEP 1-19: Remove smaller elements from the back
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()  # STEP: pop smaller indices
        dq.append(i)  # STEP: push current index
        # STEP: Remove front if out of window
        if dq[0] == i - k:
            dq.popleft()
        # STEP: Append max to result when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))  # STEP 20

📊

Sliding Window Maximum (Monotonic Deque) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the deque structure efficiently tracks maximums without redundant comparisons, which is hard to grasp from code alone.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

0

↑ pushed: 0

popElement[1]: 3

Stack (top→bottom)

1

↓ popped: [0]

pushElement[2]: -1

Stack (top→bottom)

2

1

↑ pushed: 2

no_opElement[2]: -1

Stack (top→bottom)

2

1

Contributes: 3

pushElement[3]: -3

Stack (top→bottom)

3

2

1

↑ pushed: 3

no_opElement[3]: -3

Stack (top→bottom)

3

2

1

no_opElement[3]: -3

Stack (top→bottom)

3

2

1

Contributes: 3

popElement[4]: 5

Stack (top→bottom)

4

↓ popped: [3, 2, 1]

no_opElement[4]: 5

Stack (top→bottom)

4

no_opElement[4]: 5

Stack (top→bottom)

4

Contributes: 5

pushElement[5]: 3

Stack (top→bottom)

5

4

↑ pushed: 5

no_opElement[5]: 3

Stack (top→bottom)

5

4

no_opElement[5]: 3

Stack (top→bottom)

5

4

Contributes: 5

popElement[6]: 6

Stack (top→bottom)

6

↓ popped: [5, 4]

no_opElement[6]: 6

Stack (top→bottom)

6

no_opElement[6]: 6

Stack (top→bottom)

6

Contributes: 6

popElement[7]: 7

Stack (top→bottom)

7

↓ popped: [6]

no_opElement[7]: 7

Stack (top→bottom)

7

no_opElement[7]: 7

Stack (top→bottom)

7

Contributes: 7

Key Takeaways

✓ The deque maintains indices of elements in decreasing order of their values, ensuring the front is always the maximum in the current window.

This insight is hard to see from code alone because it requires understanding how popping smaller elements preserves the maximum at the front.

✓ Elements are removed from the deque when they fall out of the sliding window range, ensuring the deque only contains relevant indices.

This pruning step is crucial to avoid stale indices and is often overlooked without visualization.

✓ The algorithm efficiently finds maximums without scanning the entire window by leveraging the monotonic property of the deque.

Watching the step-by-step popping and pushing clarifies why this approach is optimal compared to naive scanning.

Practice

1. You are given an integer array and a fixed window size k. The task is to find the contiguous subarray of length k that has the maximum average value. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window technique maintaining a running sum of the current window

B. Brute force nested loops checking all subarrays of size k

C. Dynamic programming with memoization of subproblems

D. Greedy approach selecting the largest elements regardless of position

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the maximum average of any contiguous subarray of fixed size k, which suggests examining all windows of size k.

2. Step 2: Identify optimal approach

   Sliding window maintains a running sum by adding the new element and removing the oldest, achieving O(n) time. Brute force is O(n*k), DP and greedy do not fit this fixed-size window problem optimally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in O(1) per step, total O(n) time [OK]

Hint: Sliding window updates sum in O(1) per step [OK]

Common Mistakes:

• Thinking greedy works without considering window contiguity
• Assuming DP is needed for fixed-size windows

2. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)?

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

easy

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace product and window boundaries

   Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

2. Step 2: Final count

   Total count is 8 valid subarrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected output 8 [OK]

Hint: Count increments by window size each iteration [OK]

Common Mistakes:

• Off-by-one in count increment
• Not shrinking window correctly

3. The following code attempts to find all anagrams of p in s using a sliding window with count matching optimization. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line missing decrement of window_count[left_index] when shrinking window

B. Line checking if window_count[index] == p_count[index] + 1 to decrement matches

C. Line incrementing window_count[index] when adding right character

D. Line appending left index to result when matches == 26

Solution

1. Step 1: Identify window shrinking logic

   When window size exceeds p length, left character count must be decremented.

2. Step 2: Locate missing decrement

   The code does not decrement window_count[left_index] before moving left pointer, causing incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement breaks frequency tracking [OK]

Hint: Always decrement count when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement frequency on window shrink
• Incorrect matches update logic
• Appending wrong indices

4. What is the time complexity of the sliding window approach to find the maximum sum subarray of size k in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n log k) because maintaining the window sum requires a balanced data structure.

B. O(n*k) because each window sum is recomputed from scratch for k elements.

C. O(n) because the window sum is updated in constant time for each of the n-k+1 windows.

D. O(k) because the initial sum computation dominates the runtime.

Solution

1. Step 1: Analyze the sliding window updates

   After computing the initial sum of the first k elements (O(k)), each subsequent window sum is updated by adding one element and removing one element, both O(1) operations.

2. Step 2: Calculate total time complexity

   There are (n-k) such updates, so total time is O(k) + O(n-k) = O(n). Candidates often mistake it as O(n*k) by assuming sum recomputation each time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window updates in O(1) per step -> total O(n) [OK]

Hint: Sliding window updates sum in O(1) per step -> total O(n) [OK]

Common Mistakes:

• Assuming sum is recomputed fully for each window
• Confusing initial sum cost with per-iteration cost
• Thinking data structures like heaps are needed

5. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the substring in s must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts and require window_count[c] >= t_count[c] for all c, same as original

B. Use brute force to check all substrings since counts no longer matter

C. Sort s and t and use two pointers to find minimal substring

D. Track only presence of characters from t in the window, increment have when a character appears at least once, decrement when it disappears

Solution

1. Step 1: Understand problem change

   Since counts do not matter, only presence of each character is required, so frequency counts can be replaced by boolean presence tracking.

2. Step 2: Modify sliding window logic

   Increment have when a character from t appears first time in window, decrement when it leaves. Shrink window when all characters are present.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking presence instead of counts solves the reuse variant efficiently [OK]

Hint: Track presence, not counts, when duplicates don't matter [OK]

Common Mistakes:

• Using original count-based logic
• Assuming brute force is needed
• Sorting breaks substring order