How to Solve: Sliding Window Using Deque (Monotonic Queue) – Complete Guide for FAANG Interviews

How to Solve: Sliding Window Using Deque (Monotonic Queue) – Complete Guide for FAANG Interviews

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—master it, and you’ll solve sliding window problems in linear time while others struggle with brute force. It’s the difference between ‘We’ll get back to you’ and ‘When can you start?’"

? WHAT YOU NEED TO KNOW FIRST

Before diving into Sliding Window with Deque (Monotonic Queue), ensure you understand: 1. Sliding Window Technique – Maintaining a window of elements that satisfies a condition (e.g., max/min in a subarray). 2. Deque (Double-Ended Queue) – A data structure that allows O(1) insertion/deletion at both ends. 3. Monotonic Queue – A deque where elements are kept in sorted order (increasing or decreasing) to efficiently track min/max.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these 6 steps for every sliding window + deque problem:

1. Identify the Window Type

• Fixed-size window? (e.g., "Find max in every window of size k")
• Dynamic window? (e.g., "Longest subarray where all elements ≤ k")
• Does the problem require min, max, or both?

2. Choose the Right Deque Type

• Need min? → Monotonic Increasing Deque (smallest at front).
• Need max? → Monotonic Decreasing Deque (largest at front).
• Need both? → Two deques (one for min, one for max).

3. Initialize the Deque

• Start with an empty deque.
• If the problem involves indices, store indices (not values) to track window boundaries.

4. Iterate Through the Array

• For each element nums[i]:
• Remove elements outside the current window (if using indices).
• Maintain monotonicity (remove elements from the back that violate the order).
• Add the current element to the deque.
• Record the result (if the window is valid).

5. Handle Edge Cases

• Empty input?
• Window size k = 1?
• All elements the same?
• Negative numbers?

6. Optimize & Verify Time Complexity

• Time: O(n) (each element is pushed/popped at most once).
• Space: O(k) (deque size ≤ window size).

? WORKED EXAMPLES

Example 1 – Basic: Sliding Window Maximum (LeetCode 239)

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

Solution (Step-by-Step): 1. Window Type: Fixed-size (k). 2. Deque Type: Monotonic decreasing (to track max). 3. Initialize: Empty deque. 4. Iterate:
- Remove indices outside the current window (i - k).
- Remove elements from the back that are ≤ nums[i] (they can’t be max).
- Add i to the deque.
- If i ≥ k-1, record nums[deque[0]] (front is the max). 5. Edge Cases:
- k = 1 → Return nums as-is.
- nums = [] → Return []. 6. Time: O(n), Space: O(k).

Python Code:

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 elements smaller than current from the back

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

            dq.pop()

        dq.append(i)

        # Record max once window is valid

        if i >= k - 1:

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

    return res

Why This Works: - The deque always maintains the largest element at the front for the current window. - By removing smaller elements from the back, we ensure O(1) max access at any time.

Example 2 – Medium: Longest Subarray with All Elements ≤ K

Problem: Given an array nums and an integer k, find the length of the longest subarray where all elements are ≤ k.

Solution (Step-by-Step): 1. Window Type: Dynamic (expands/shrinks). 2. Deque Type: Monotonic increasing (to track min). 3. Initialize: Empty deque, left = 0, max_len = 0. 4. Iterate:
- While nums[i] > k, move left forward (shrink window).
- Remove elements from the back that are ≥ nums[i] (they can’t be min).
- Add i to the deque.
- Update max_len = max(max_len, i - left + 1). 5. Edge Cases:
- All elements ≤ k → Return len(nums).
- nums = [] → Return 0. 6. Time: O(n), Space: O(n) (worst case).

Python Code:

from collections import deque

def longestSubarray(nums, k):

    dq = deque()

    left = 0

    max_len = 0

    for i, num in enumerate(nums):

        # Remove elements > k from the left

        while num > k:

            left += 1

            if dq and dq[0] < left:

                dq.popleft()

            num = nums[i]  # Re-check after moving left

        # Maintain monotonic increasing deque

        while dq and nums[dq[-1]] >= num:

            dq.pop()

        dq.append(i)

        max_len = max(max_len, i - left + 1)

    return max_len

Why This Works: - The deque tracks the smallest element in the current window, ensuring we can shrink the window efficiently when nums[i] > k.

Example 3 – Hard/Follow-up: Subarray Sum Equals K (Linear Time)

Problem: Given an array nums and an integer k, find the number of subarrays where the sum equals k.

Solution (Step-by-Step): 1. Window Type: Dynamic (prefix sums). 2. Deque Type: Monotonic increasing (to track prefix sums). 3. Initialize: prefix = {0: 1}, sum = 0, count = 0. 4. Iterate:
- sum += nums[i].
- If sum - k exists in prefix, add prefix[sum - k] to count.
- Maintain a monotonic deque of prefix sums to optimize lookups (optional for follow-up).
- Update prefix[sum]. 5. Edge Cases:
- nums = [] → Return 0.
- All elements 0 → Return n(n+1)/2. 6. Time: O(n), Space: O(n).

Python Code:

from collections import defaultdict

def subarraySum(nums, k):

    prefix = defaultdict(int)

    prefix[0] = 1

    sum_ = 0

    count = 0

    for num in nums:

        sum_ += num

        if sum_ - k in prefix:

            count += prefix[sum_ - k]

        prefix[sum_] += 1

    return count

Follow-up (Using Deque for Optimization): If the problem requires subarrays of length ≤ m, use a deque to track valid prefix sums in a sliding window.

Why This Works: - The prefix sum technique allows O(1) lookups for sum - k. - The deque optimizes the window when constraints are added (e.g., max subarray length).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Sliding window with deque is all about tracking min/max in linear time. Here’s the playbook:

1. Pick your deque: Increasing for min, decreasing for max.
2. Maintain the window: Remove out-of-bounds indices first.
3. Keep it monotonic: Pop from the back before appending.
4. Record results: Once the window is valid, take the front of the deque.
5. Edge cases: Empty input, k=1, all elements equal.

This pattern shows up in LeetCode 239, 862, 1425—and it’s a FAANG favorite. If you see ‘sliding window’ or ‘subarray min/max’, reach for the deque. Now go crush that interview!

? Final Notes

• Practice Problems:
• LeetCode 239 (Sliding Window Maximum)
• LeetCode 862 (Shortest Subarray with Sum at Least K)
• LeetCode 1425 (Constrained Subsequence Sum)
• Time to Master: 3-5 problems (you’ll recognize the pattern instantly).
• Whiteboard Tip: Draw the deque at each step to visualize monotonicity.

Now go solve it like a pro! ?