You are given an array of integers nums, there is a sliding window of size k which is moving 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 max sliding window.

Examples

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

Thinking Process

  1. Monotonic Deque: Maintain indices in decreasing order of values
  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

Time Complexity: O(n) - Each element is added and removed at most once
Space Complexity: O(k) - Deque stores at most k elements

Use a deque (double-ended queue) to maintain indices of elements in decreasing order of their values. This allows O(1) access to the maximum element in the current window.

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        rtn = []
        q = deque()  # will store indices
        
        for i in range(len(nums)):
            # Remove indices outside the window
            while q and q[0] < i - k + 1:
                q.popleft()
            
            # Remove smaller values (they can't be max)
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            
            q.append(i)
            
            # Add result once window is full
            if i >= k - 1:
                rtn.append(nums[q[0]])
        
        return rtn

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: 1. Monotonic Deque: Maintain indices in decreasing order of values

How the code works:

  1. Monotonic Deque: Maintain indices in decreasing order of values
    • Maintain a window [left, right] satisfying a constraint.
    • Expand right to grow; shrink left when invalid.
    • Fixed window: slide both pointers together.

Walkthrough — input nums = [1,3,-1,-3,5,3,6,7], k = 3, expected output [3,3,5,5,6,7]:

Window position Max ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

| Aspect | Complexity | |——–|————| | Time | O(n) - Each element is added once and removed at most once | | Space | O(k) - Deque stores at most k indices |

Algorithm Breakdown

1. Initialize

from collections import deque

rtn: list[int] = []
q: deque[int] = deque()
  • rtn: Result array to store maximums
  • q: Deque storing indices in decreasing order of values

2. Remove Out-of-Window Indices

while q and q[0] < i - k + 1:
    q.popleft()
  • Window starts at i - k + 1
  • Remove indices that are before the window start

3. Remove Smaller Elements

while q and nums[q[-1]] < nums[i]:
    q.pop()
  • Remove indices whose values are smaller than nums[i]
  • These elements can never be the maximum in any future window
  • Maintains decreasing order in deque

4. Add Current Index

q.append(i)
  • Add current index to deque

5. Record Maximum

if i >= k - 1:
    rtn.append(nums[q[0]])
  • When window is complete (i >= k - 1), add maximum to result
  • Maximum is always at q.front()

Complexity

| Aspect | Complexity | |——–|————| | Time | O(n) - Each element is added once and removed at most once | | Space | O(k) - Deque stores at most k indices |

Why O(n) Time?

  • Each index is added to deque exactly once: O(n)
  • Each index is removed from deque at most once: O(n)
  • Total: O(n) operations

Why Monotonic Deque is Optimal

  1. Linear Time: Each element is processed exactly once
  2. Constant Operations: Deque operations (push, pop) are O(1) amortized
  3. Efficient Removal: Removing smaller elements early prevents unnecessary comparisons
  4. Direct Access: Maximum is always at front, no need to search

Common Mistakes

  1. k = 1: Each window has one element → return all elements
  2. k = nums.size(): Single window → return maximum of entire array
  3. All increasing: [1,2,3,4,5] → deque always has one element
  4. All decreasing: [5,4,3,2,1] → deque contains all indices initially

  5. All same: [3,3,3,3] → all 3s in result

  6. Forgetting to remove out-of-window indices: Must check q.front() < i - k + 1
  7. Wrong comparison: Should be nums[q.back()] < nums[i] not <= (handles duplicates)
  8. Adding before window complete: Only add to result when i >= k - 1
  9. Using values instead of indices: Deque should store indices to check window boundaries

Optimization Tips

Early Termination Check

def max_sliding_window_bruteforce(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    return [max(nums[i : i + k]) for i in range(n - k + 1)]

Memory Optimization

The deque approach is already optimal. For very large arrays, you could use a fixed-size array, but deque is more flexible and still O(k) space.

Pattern Recognition

This problem demonstrates the Monotonic Deque pattern:

  • Maintain a deque with elements in monotonic order (increasing or decreasing)
  • Remove elements that violate the monotonic property
  • Use deque to efficiently query extreme values (min/max) in a sliding window

Applications:

  • Sliding window maximum/minimum
  • Next greater/smaller element
  • Range queries in sliding windows
  • Dynamic programming optimizations

Code Quality Notes

  1. Readability: Clear variable names (q for queue, rtn for result)
  2. Efficiency: Optimal time and space complexity
  3. Correctness: Handles all edge cases properly
  4. Maintainability: Well-structured code with clear comments

Implementation Details

Why Store Indices Instead of Values?

Storing indices allows us to:

  1. Check if an element is outside the window: q.front() < i - k + 1
  2. Access the value: nums[q.front()]
  3. Compare values: nums[q.back()] < nums[i]

Why Remove from Back?

We maintain decreasing order, so when we encounter a larger value:

  • All smaller values at the back can never be maximum
  • Removing from back maintains the monotonic property
  • Front always contains the maximum index

Why Check i >= k - 1?

  • Window of size k starting at index i covers [i, i+k-1]
  • When i = k - 1, window is [0, k-1] (first complete window)
  • Before this, window is incomplete, so we don’t record maximum

This problem is a classic example of using a monotonic deque to efficiently solve sliding window problems. The key insight is maintaining a data structure that automatically keeps track of the maximum while efficiently removing outdated elements.

Key Takeaways

  1. Monotonic Deque: Maintain indices in decreasing order of values
  2. Remove Out-of-Window: Remove indices i - k + 1 from the front
  3. Remove Smaller Elements: Remove indices whose values are smaller than current (they can never be maximum)
  4. Front is Maximum: q.front() always points to the maximum element in current window
  5. Amortized O(1): Each element is added and removed at most once

References

Template Reference