Sliding Window Maximum

How it works

A deque helps us efficiently track the maximum inside the sliding window.
The key idea is to keep the deque storing indices of elements in decreasing order of their values.
This guarantees that:

• The front of the deque always holds the index of the current window’s maximum.
• Smaller elements behind a bigger one are useless (they can never become the max later),
  so we remove them when pushing a new number.
• If the element at the front falls out of the window, we remove it.

By maintaining this structure, each element is added and removed at most once, giving an optimal solution.

Steps

1. Use a deque to store indices of elements in decreasing order of their values.
2. Expand the window by moving the right pointer:
   • Before inserting the new index, remove indices whose values are smaller than the new value (they cannot be future maximums).
   • Add the new index to the deque.
3. If the left pointer passes the front index, remove it (it's outside the window).
4. Once the window reaches size k, the front of the deque represents the maximum — add it to the output.
5. Slide the window and repeat.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Choosing Between Values and Indices in the Deque

The deque can store either indices or values. Indices make it straightforward to detect when an element leaves the window by comparing its position with the left boundary.

A value-only deque is also correct when the original array is available. Keep duplicate values by removing only strictly smaller values from the back. When the window moves, remove one value from the front if it equals the outgoing value nums[l]. If duplicates are discarded without storing indices or counts, the deque can remove a value that still has another occurrence inside the window.

Incorrect Window Boundary Checks

Many solutions fail by using wrong conditions for when to start recording results or when to shrink the window. The first valid window exists when right >= k - 1 (or equivalently right + 1 >= k). Off-by-one errors here cause either missing the first window's maximum or including results before the window is fully formed.

Not Maintaining Decreasing Order in Deque

The deque must remain monotonic in decreasing order of value. For an index deque, both < and <= are correct when removing elements from the back. Using < retains equal values, while <= discards the older equal value because the newer occurrence has the same value and expires later. For a value-only deque without counts, use < so duplicate occurrences are retained. Forgetting to remove smaller values is the actual error because the front may no longer represent the current window's maximum.

Forgetting to Handle the Output Array Size

The number of windows is n - k + 1, not n or n - k. Allocating an output array of the wrong size leads to index out of bounds errors or missing results. This is especially problematic when k equals the array length, where there should be exactly one result.

Incorrect Segment Tree Range Queries

When using segment trees, a frequent mistake is confusing inclusive versus exclusive range boundaries. The query range [i, i + k - 1] is inclusive on both ends for a window starting at index i. Mixing up these boundaries causes queries to include elements outside the window or miss elements at the boundaries.

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        q = deque()  # index
        l = r = 0

        while r < len(nums):
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            if l > q[0]:
                q.popleft()

            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1

        return output

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> output(n - k + 1);
        deque<int> q;
        int l = 0, r = 0;

        while (r < n) {
            while (!q.empty() && nums[q.back()] < nums[r]) {
                q.pop_back();
            }
            q.push_back(r);

            if (l > q.front()) {
                q.pop_front();
            }

            if ((r + 1) >= k) {
                output[l] = nums[q.front()];
                l++;
            }
            r++;
        }

        return output;
    }
};