Sliding Window Maximum LeetCode Solution (Hard) (2026)

Approach Summary

Use a monotonic deque storing indices. Maintain decreasing order of values; the front is always the maximum of the current window.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

To find the maximum element in every sliding window of size k in linear time O(n), we maintain a monotonic deque (double-ended queue) storing array indices. As we traverse the array from left to right, we maintain two key invariants in the deque: (1) indices in the deque are always within the current window boundary [i - k + 1, i], so elements that have fallen outside the window are popped from the front; and (2) elements in the deque are maintained in strictly descending order of their values. When considering each new element nums[i], we pop elements from the back of the deque as long as they are strictly smaller than or equal to nums[i], because they can never be the maximum in any current or future window that contains nums[i]. Once the invariants are maintained, the element at the front of the deque is always the maximum for the current window of size k.

Time Complexity: O(n) because each element is pushed into the deque exactly once and popped at most once. Space Complexity: O(k) auxiliary space for the deque storing at most k indices.

Solution Code

Solution

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!q.isEmpty() && q.peekFirst() <= i - k) q.pollFirst();
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) q.pollLast();
            q.offerLast(i);
            if (i >= k - 1) res[i - k + 1] = nums[q.peekFirst()];
        }
        return res;
    }
}

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            while (!q.empty() && q.front() <= i - k) q.pop_front();
            while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        res = []
        for i, n in enumerate(nums):
            while q and q[0] <= i - k:
                q.popleft()
            while q and nums[q[-1]] < n:
                q.pop()
            q.append(i)
            if i >= k - 1:
                res.append(nums[q[0]])
        return res

var maxSlidingWindow = function(nums, k) {
    const q = [];
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        while (q.length && q[0] <= i - k) q.shift();
        while (q.length && nums[q[q.length - 1]] < nums[i]) q.pop();
        q.push(i);
        if (i >= k - 1) res.push(nums[q[0]]);
    }
    return res;
};

Edge Cases to Watch

k = 1: the answer is the array itself
Array elements strictly decreasing: deque contains k elements
Array elements strictly increasing: deque contains 1 element at all times
Negative numbers in nums: comparisons must preserve negative values

Algorithmic Pattern

Master the Sliding Window Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Sliding Window pattern.

Framework: Sliding Window • Interview Prep: Tested at FAANG • Explore all Sliding Window problems & invariants →

How to Recognize This Pattern

Fixed window size
Max in each window

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(k)

Frequently Asked Questions

What is the optimal time and space complexity for Sliding Window Maximum?

The optimal solution for Sliding Window Maximum achieves O(n) runtime complexity and requires O(k) auxiliary space. Time Complexity: O(n) because each element is pushed into the deque exactly once and popped at most once. Space Complexity: O(k) auxiliary space for the deque storing at most k indices.

How do I identify that Sliding Window Maximum requires the Sliding Window pattern?

In technical interviews, look for key problem signals: Fixed window size; Max in each window. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Sliding Window strategy.

What critical edge cases must be handled in Sliding Window Maximum?

Essential edge cases to verify include: k = 1: the answer is the array itself; Array elements strictly decreasing: deque contains k elements; Array elements strictly increasing: deque contains 1 element at all times; Negative numbers in nums: comparisons must preserve negative values. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Sliding Window Maximum?

Sliding Window Maximum is a Hard-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Microsoft.

Sliding Window Maximum LeetCode Solution