Sliding Window Maximum (Monotonic Deque)

📋

Problem

Imagine monitoring the highest temperature in every hour-long window throughout a day to detect heat spikes efficiently.

Given an integer array nums and an integer k, there is a sliding window of size k which moves from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the maximum of the k numbers in the window.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

Edge cases: k = 1 → output is the array itselfAll elements equal → output is repeated elementStrictly increasing array → max is last element in each window

</>

IDE

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:public int[] maxSlidingWindow(int[] nums, int k)vector<int> maxSlidingWindow(vector<int>& nums, int k)function maxSlidingWindow(nums, k)

def maxSlidingWindow(nums, k):
    # Write your solution here
    pass

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    // Write your solution here
    return {};
}

function maxSlidingWindow(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,3,3,5,5,6]Not removing elements that fall out of the sliding window from the data structure.✅ Remove indices from the front of the deque if they are outside the current window (index <= i-k).

Wrong: [3,3,5,5,6,7,7]Incorrect window size or off-by-one error causing extra output elements.✅ Ensure output length is n-k+1 and loop runs correctly for i in range(n).

Wrong: [3,3,5,5,6]Greedy approach picking max only at window start without updating as window slides.✅ Use a monotonic deque to update max dynamically as window slides.

Wrong: []Not handling k=1 or single element input correctly, returning empty output.✅ Return nums directly if k=1 or handle single element arrays properly.

Wrong: [2,2]Removing equal elements prematurely from deque causing shorter output.✅ Allow equal elements to remain in deque to maintain correct max.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Think about common algorithmic pitfalls like greedy mistakes and off-by-one errors.

Optimize your solution to run in linear time using a monotonic deque.

t1_01basic

Input{"nums":[1,3,-1,-3,5,3,6,7],"k":3}

Expected[3,3,5,5,6,7]

⏱ Performance - must finish in 2000ms

The sliding windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. Their maximums are 3, 3, 5, 5, 6, 7 respectively.

💡 Consider how to track the maximum efficiently as the window slides.

💡 Use a data structure that keeps elements in decreasing order to get max in O(1).

💡 Implement a monotonic deque that pops smaller elements from the back and removes out-of-window indices from the front.

Why it failed: Output differs from expected max values per window; likely not maintaining correct max or window boundaries. Fix by using a monotonic deque that removes elements outside the current window and smaller elements behind the current index.

✓ Correctly computes maximum for each sliding window using monotonic deque.

t1_02basic

Input{"nums":[9,11,8,5,7,10],"k":2}

Expected[11,11,8,7,10]

⏱ Performance - must finish in 2000ms

Sliding windows: [9,11], [11,8], [8,5], [5,7], [7,10]. Maximums are 11, 11, 8, 7, 10 respectively.

💡 Try simulating the sliding window and tracking max for each window.

💡 Check if your data structure correctly removes elements that fall out of the window.

💡 Ensure you pop smaller elements from the deque's back before adding new elements.

Why it failed: Incorrect max values due to not removing indices outside the window or not maintaining decreasing order in deque. Fix by popping indices from front if out of window and popping smaller elements from back before pushing new index.

✓ Correctly handles sliding window max for different input sizes and values.

t2_01edge

Input{"nums":[5],"k":1}

Expected[5]

⏱ Performance - must finish in 2000ms

Single element window size 1 returns the element itself.

💡 What happens when the window size equals the array length or is 1?

💡 The maximum in each window of size 1 is the element itself.

💡 Return the input array directly when k=1.

Why it failed: Fails to handle k=1 case, possibly overcomplicating or returning empty array. Fix by returning nums directly when k=1.

✓ Correctly returns input array when window size is 1.

t2_02edge

Input{"nums":[2,2,2,2,2],"k":3}

Expected[2,2,2]

⏱ Performance - must finish in 2000ms

All elements equal; max in every window is the same repeated element.

💡 How does your algorithm handle equal elements in the window?

💡 Ensure the deque does not remove equal elements incorrectly.

💡 Maintain indices in deque even if values are equal to preserve correct max.

Why it failed: Incorrect max due to removing equal elements prematurely from deque. Fix by allowing equal elements to remain in deque to maintain correct max.

✓ Correctly handles windows with all equal elements.

t2_03edge

Input{"nums":[1,2,3,4,5],"k":5}

Expected[5]

⏱ Performance - must finish in 2000ms

Window size equals array length; max is the max of entire array.

💡 What if the window size equals the array length?

💡 The max is the maximum element of the entire array.

💡 Your algorithm should handle this without errors or empty output.

Why it failed: Fails to handle window size equal to array length, possibly returning empty or partial output. Fix by ensuring the loop runs correctly for n-k+1 windows including full length.

✓ Correctly returns max of entire array when window size equals array length.

t3_01corner

Input{"nums":[1,3,1,2,0,5],"k":3}

Expected[3,3,2,5]

⏱ Performance - must finish in 2000ms

Tests correct removal of elements outside window and maintaining max with duplicates and smaller elements.

💡 Check if your deque removes indices that are out of the current window.

💡 Verify that smaller elements behind the current index are popped to maintain decreasing order.

💡 Fix by popping from front if index < i-k+1 and popping from back while nums[deque.back()] < nums[i].

Why it failed: Fails due to not removing out-of-window indices or not popping smaller elements behind current index. Fix by properly maintaining deque boundaries and order.

✓ Correctly handles sliding window max with duplicates and out-of-window removals.

t3_02corner

Input{"nums":[9,7,2,4,6,8,2,1],"k":4}

Expected[9,7,6,8,8]

⏱ Performance - must finish in 2000ms

Tests greedy trap where picking local max only fails; must maintain global max in window.

💡 Beware of greedy approach that picks max at start of window without updating.

💡 Use a monotonic deque to track max candidates dynamically.

💡 Fix by updating max as window slides, removing expired indices.

Why it failed: Fails greedy trap by not updating max when window slides. Fix by using deque to track max candidates and remove expired indices.

✓ Correctly avoids greedy trap and updates max dynamically.

t3_03corner

Input{"nums":[4,3,5,4,3,3,6,7],"k":3}

Expected[5,5,5,4,6,7]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in window boundaries and deque maintenance.

💡 Check your window start and end indices carefully.

💡 Ensure you remove indices from deque front when they fall out of the window.

💡 Fix by removing indices deque[0] if deque[0] <= i-k before adding new index i.

Why it failed: Off-by-one error causing incorrect window max or deque maintenance. Fix by correctly removing indices outside window before adding new index.

✓ Correctly handles window boundaries and deque updates.

t4_01performance

Input{"nums":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with decreasing values and window size k=50 to test O(n) monotonic deque efficiency within 2 seconds.

💡 Brute force O(n*k) will time out on large inputs.

💡 Use a monotonic deque to achieve O(n) time complexity.

💡 Avoid nested loops; maintain deque to track max efficiently.

Why it failed: TLE due to O(n*k) brute force or inefficient data structure. Fix by implementing O(n) monotonic deque approach.

✓ Algorithm runs within time limit using O(n) monotonic deque approach.

Practice

1. Consider the following Python code implementing the optimal sliding window solution for the fruits problem. What is the returned value when the input is [1, 2, 1]?

def totalFruit(fruits):
    basket = {}
    left = 0
    max_length = 0
    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace iterations for input [1, 2, 1]

   Right=0: basket={1:1}, max_length=1; Right=1: basket={1:1,2:1}, max_length=2; Right=2: basket={1:2,2:1}, max_length=3.

2. Step 2: No window shrinking needed as basket size never exceeds 2

   Final max_length is 3, the length of entire array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All fruits fit in one window of length 3 [OK]

Hint: Count window length when basket size ≤ 2 [OK]

Common Mistakes:

• Off-by-one in window length
• Shrinking window unnecessarily
• Miscounting basket size

2. What is the time complexity of the optimal sliding window solution for the fruits problem, given an input array of length n? Assume fruit types are arbitrary integers but the number of distinct fruit types in the window is limited to two.

medium

A. O(n) because each element is visited at most twice by the two pointers

B. O(n log n) due to maintaining the hash map keys in sorted order

C. O(n²) because the inner while loop can run multiple times per outer iteration

D. O(n * k) where k is the number of distinct fruit types in the array

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window.

2. Step 2: Each element is added and removed at most once

   Thus total operations are proportional to 2n, which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hashmap is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to n²
• Thinking hashmap operations add log n
• Confusing distinct fruit count with input size

3. What is the time complexity of the optimal sliding window solution for the Longest Repeating Character Replacement problem, assuming the input string length is n and the character set size is fixed (e.g., 26 uppercase letters)?

medium

A. O(n) because each character is visited at most twice by left and right pointers

B. O(n^2) because the window can shrink and expand multiple times

C. O(n * k) because the inner loop depends on the number of allowed replacements

D. O(n) but with O(n) auxiliary space due to frequency map storage

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves from 0 to n-1 once. Left pointer only moves forward when window is invalid, also at most n times.

2. Step 2: Consider frequency array and fixed character set

   Frequency array is fixed size (26), so updates are O(1). No nested loops over n inside main loop.

3. Step 3: Analyze space complexity

   The frequency array uses O(1) space since the character set is fixed, not O(n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-pointer linear scan with fixed-size frequency array [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Thinking k affects inner loop complexity
• Confusing frequency map space with time complexity

4. What is the time complexity of the optimal sliding window solution that uses a queue to track zero positions for the Max Consecutive Ones III problem, given an input array of length n and integer k?

medium

A. O(n * k) because each zero can cause multiple window shifts

B. O(n) because each element is visited at most twice by the two pointers

C. O(n^2) because the queue operations inside the loop cause nested behavior

D. O(k) because the queue size is limited to k zeros only

Solution

1. Step 1: Identify loop behavior

   The right pointer iterates over all n elements once, and the left pointer only moves forward when zeros exceed k.

2. Step 2: Analyze queue operations and pointer moves

   Each zero index is enqueued once and dequeued once, so total operations are O(n). However, each zero can cause the left pointer to move multiple times in worst case, leading to O(n * k) complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   While the queue operations are O(n), the window shifts can multiply by k in worst cases [OK]

Hint: Consider worst-case window shifts caused by zeros [OK]

Common Mistakes:

• Assuming strictly linear without considering multiple shifts
• Confusing queue size with total operations
• Ignoring worst-case scenarios

5. Suppose the problem is modified so that the array can contain negative numbers as well as positive numbers. Which of the following statements about applying the sliding window approach to find the minimum size subarray sum ≥ target is true?

hard

A. Sliding window fails because negative numbers can cause the sum to decrease unpredictably, breaking the monotonic window property

B. Sorting the array first allows sliding window to work correctly with negatives

C. Sliding window still works unchanged because the sum can be adjusted dynamically

D. Prefix sums with binary search is invalid because sums can be negative

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on sums increasing as right pointer moves forward and shrinking from left to reduce sum, which requires all positive numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can decrease sum inside the window unpredictably, so shrinking or expanding window does not guarantee monotonic sum changes, breaking the approach.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window requires non-negative numbers for correctness [OK]

Hint: Negative numbers break sliding window monotonic sum property [OK]

Common Mistakes:

• Assuming sliding window works with negatives
• Thinking sorting fixes contiguous subarray sums
• Believing prefix sums binary search fails with negatives