How to Solve: Sliding Window Maximum

How to Solve: Sliding Window Maximum

(A Complete FAANG-Level Interview Guide)

? Introduction

"This single pattern appears in 1 out of every 3 onsite interviews—master it, and you’ll solve problems in O(n) time with O(k) space, proving you can optimize beyond brute force."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Sliding Window Maximum, ensure you understand: 1. Monotonic Deques – A deque (double-ended queue) where elements are kept in a specific order (e.g., decreasing) to enable O(1) max/min queries. 2. Sliding Window Basics – Fixed-size window traversal (e.g., subarrays of size k). 3. Time Complexity Analysis – Why nested loops are O(n²) and how to reduce to O(n).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeat this checklist for every sliding window max problem.)

1. Clarify the Problem
2. Is the window size fixed (e.g., k) or variable?
3. Are there duplicates? (Affects deque logic.)

4. Is the array circular? (May require prefix/suffix max.)

5. Brute Force Baseline

6. For each window, scan all k elements → O(nk) time.

7. Write this first to validate correctness.

8. Optimize with Monotonic Deque

9. Initialize an empty deque.

10. Traverse the array with index i:

    • Remove indices outside the window (front of deque).
    • Maintain decreasing order (remove smaller elements from the back).
    • Add current index to the deque.
    • Record max (front of deque) once the window is full.

11. Edge Cases

12. k = 1 → Return the array itself.
13. k = n → Return the global max.

14. Empty array or k = 0 → Return [].

15. Time/Space Complexity

16. Time: O(n) (each element pushed/popped once).

17. Space: O(k) (deque holds at most k elements).

18. Test with Examples

19. Small case (e.g., [1,3,-1,-3,5,3,6,7], k=3).
20. All duplicates (e.g., [2,2,2,2], k=2).

21. Negative numbers (e.g., [-7,-8,-1,-2], k=2).

22. Follow-Up Questions

23. "What if the window size is dynamic?" → Use two pointers + deque.
24. "What if the array is circular?" → Precompute prefix/suffix max.

✏️ WORKED EXAMPLES

Example 1 – Basic (Fixed Window)

Problem: Given an array nums and integer k, return the max of every sliding window of size k.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7]

Step-by-Step Solution

1. Brute Force (Baseline):
   python
def maxSlidingWindow(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums)-k+1)]

2. Time: O(nk) (slow for large n).

3. Optimized (Monotonic Deque):
   ```python
   from collections import deque

def maxSlidingWindow(nums, k):
dq = deque()
res = []
for i, num in enumerate(nums):
# Remove indices outside the window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove smaller elements from the back
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# Record max once window is full
if i >= k - 1:
res.append(nums[dq[0]])
return res
```
- Why this works:
- The deque stores indices in decreasing order of values.
- The front is always the max of the current window.
- Each element is pushed/popped at most once → O(n) time.

1. Complexity:
2. Time: O(n) (each element processed once).
3. Space: O(k) (deque holds up to k elements).

Example 2 – Medium (Duplicates & Edge Cases)

Problem: Same as above, but handle duplicates and edge cases.

Input: nums = [7,2,4], k = 2 Output: [7,4]

Solution

from collections import deque

def maxSlidingWindow(nums, k):

    if not nums:

        return []

    dq = deque()

    res = []

    for i, num in enumerate(nums):

        while dq and dq[0] <= i - k:

            dq.popleft()

        while dq and nums[dq[-1]] < num:  # Strictly decreasing

            dq.pop()

        dq.append(i)

        if i >= k - 1:

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

    return res

• Key Insight:
• Duplicates are handled naturally (e.g., [2,2,2] → deque keeps the rightmost 2).
• Edge case k=1 → deque always has the current element.

Example 3 – Hard (Dynamic Window Size)

Problem: Given an array nums and integer k, return the max of every subarray of size ≤ k.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1,3,3,5,5,6,7] (includes windows of size 1, 2, and 3)

Solution

from collections import deque

def maxSlidingWindowVariable(nums, k):

    dq = deque()

    res = []

    for i, num in enumerate(nums):

        while dq and dq[0] <= i - k:

            dq.popleft()

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

            dq.pop()

        dq.append(i)

        res.append(nums[dq[0]])  # Record max for every window ending at i

    return res

• Why this works:
• The deque still maintains the max for the current window.
• We record the max for every position (not just when i >= k-1).
• Complexity:
• Time: O(n) (same as fixed window).
• Space: O(k).

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second cheat sheet for Sliding Window Maximum: 1. Brute force is O(nk) — too slow for large inputs. 2. Monotonic deque is the optimal O(n) solution:
- Remove out-of-window indices from the front.
- Maintain decreasing order by popping smaller elements from the back.
- Record the front of the deque once the window is full. 3. Edge cases: k=1, k=n, duplicates, negatives. 4. Follow-ups: Dynamic window? Circular array? Use two pointers or prefix/suffix max. 5. Avoid traps: Don’t use a heap, store indices (not values), and handle duplicates with < (not <=).

Walk in, code the deque, and own the interview."

? FINAL NOTES

• Practice Problems:
• LeetCode 239. Sliding Window Maximum
• LeetCode 1425. Constrained Subsequence Sum (hard follow-up)
• LeetCode 862. Shortest Subarray with Sum at Least K (monotonic deque + prefix sum)
• Whiteboard Tip: Draw the deque at each step to visualize the max.

You’re now ready to solve any sliding window max problem in under 15 minutes. ?