Sliding Window Maximum

Problem Description

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

Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

Monotonic Queue (Deque)

To solve this in O(n) time instead of O(n * k), we maintain a double-ended queue (deque) that stores the indices of elements in the sliding window. We maintain the queue in a monotonically decreasing order of their corresponding values. When a new element nums[i] is processed:

1. While the deque is not empty and the element at the back of the queue is smaller than nums[i], we pop elements from the back (since they can never be the maximum in any future window).
2. We push the current index i onto the back of the deque.
3. We check if the element at the front of the deque has slid out of the window (front_index <= i - k). If so, we pop it.
4. The element at the front of the deque is always the maximum of the current window. Once the window reaches size k, we copy this maximum to our result.

Solution 1: Monotonic Deque

Maintain a decreasing deque of active indices to query the sliding maximum in O(1) time.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // stores indices

        int ri = 0;
        for (int i = 0; i < n; i++) {
            // Remove indices that are out of the current window
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove elements smaller than the current element from the back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Copy the maximum once window size reaches k
            if (i >= k - 1) {
                result[ri++] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        if not nums:
            return []
            
        n = len(nums)
        result = []
        q = deque()  # stores indices
        
        for i in range(n):
            # Remove indices that have slid out of the window
            if q and q[0] <= i - k:
                q.popleft()
                
            # Remove elements smaller than the current element from the back
            while q and nums[q[-1]] < nums[i]:
                q.pop()
                
            q.append(i)
            
            # Once the window is fully initialized, append the maximum
            if i >= k - 1:
                result.append(nums[q[0]])
                
        return result

#include <vector>
#include <deque>

class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::vector<int> result;
        if (nums.empty()) return result;
        std::deque<int> dq; // stores indices

        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

Complexity Analysis

• Time Complexity: O(n) because each index is pushed onto the deque once and popped at most once.
• Space Complexity: O(k) auxiliary space to store elements in the deque.

Where It Breaks

This solution requires direct index mapping. If the stream is infinite and data points have irregular timestamps rather than integer slots, a Segment Tree or a Heap with lazy deletions is required.

Common Mistakes

• Incorrect queue cleaning: Popping elements from the front when they are smaller instead of from the back. The back of the queue must be checked to maintain the decreasing order.
• Storing values instead of indices: Storing raw values in the deque makes it impossible to check if the maximum has slid out of the window range.

Frequently Asked Questions

Why does this run in O(n) time? Every element is added to the queue once and removed at most once. The total number of queue insertions and deletions is bounded by 2n, giving a linear time complexity.

Can we use a Max Heap? Yes. You can push elements to a Max Heap and lazily remove the top elements if their index is outside the window. This takes O(n log n) time, which is less optimal than the O(n) deque approach.

← All Problems