Problem statement

You are given an array nums and a window of size k sliding from left to right, one position at a time. Return an array of the maximum of each window.

Example 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Example 2

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

Constraints

• 1 <= nums.length <= 40
• -100 <= nums[i] <= 100
• 1 <= k <= nums.length

Hints for Sliding Window Maximum

1. Hint 1

   A monotonic decreasing deque of indices keeps the window max at its front.

2. Hint 2

   Pop smaller elements from the back before pushing; drop the front when it leaves the window.

How to solve Sliding Window Maximum

Rescanning each window is O(n·k). The fix is a monotonic deque holding indices whose values decrease from front to back: the front is always the current window's maximum, and any element smaller than a newer one can be discarded forever, because the newer element is both larger and stays in the window longer.

Approach

1. Keep a deque of indices, values decreasing from front to back.
2. Before pushing i, pop from the back while the value there is less than or equal to nums[i] — those can never be a maximum again.
3. Push i at the back.
4. Pop from the front if that index has fallen out of the window (front <= i - k).
5. Once i >= k - 1, the value at the front index is that window's maximum — record it.

Why it works

The discard rule is the heart of it: if j < i and nums[j] <= nums[i], then any window containing j and i is dominated by i, and j expires first — so j is permanently useless. What remains is a strictly decreasing sequence, whose front is by definition the largest still in range. Each index is pushed once and popped at most once, so despite the inner loops the total work is linear.

Complexity

• Time — O(n)
• Space — O(k)

Pitfalls

• The deque stores indices, not values — you need positions to know when an element leaves the window.
• Pop equal values from the back too (<=); keeping them is harmless for correctness but wastes space.
• Evict the stale front by index (front <= i - k), not by comparing values.
• Only start recording once the first full window has formed at i == k - 1.

Reference solution

Python

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    out = []
    dq = deque()
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Java

public static int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] dq = new int[n];
    int head = 0, tail = 0;
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        while (tail > head && nums[dq[tail - 1]] <= nums[i]) tail--;
        dq[tail++] = i;
        if (dq[head] <= i - k) head++;
        if (i >= k - 1) out.add(nums[dq[head]]);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = (int) nums.size();
    vector<int> dq(n);
    int head = 0, tail = 0;
    vector<int> out;
    for (int i = 0; i < n; i++) {
        while (tail > head && nums[dq[tail - 1]] <= nums[i]) tail--;
        dq[tail++] = i;
        if (dq[head] <= i - k) head++;
        if (i >= k - 1) out.push_back(nums[dq[head]]);
    }
    return out;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard