Sliding Window Maximum

HardSliding WindowNeetCode 150SeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given an integer array nums and an integer k. Consider every contiguous subarray of length k: the one starting at index 0, the one starting at index 1, and so on, up to the one that ends at the last element. Return an array holding the largest value of each of those subarrays, in order of their starting index, so the result has n - k + 1 entries. Values can be negative and can repeat.

Examples

nums = [1,3,-1,-3,5,3,6,7], k = 3 returns [3,3,5,5,6,7]

The subarray at indices 2 to 4 is [-1,-3,5], so the third answer is 5.

The length-3 subarrays are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6] and [3,6,7]. Their largest values, in order, are 3, 3, 5, 5, 6 and 7.

nums = [1], k = 1 returns [1]

With k = 1 every element is a subarray on its own, so each maximum is just that element.

Constraints

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

Hints

Hint 1

Rescanning all k elements for every position costs O(n * k). When a new, larger element arrives, which older elements can never be the answer again?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Keep a deque of indices whose values strictly decrease from front to back, so the front is always the maximum of the current window. For each i, drop the front if it is i - k (it just left the window), pop from the back every index whose value is <= nums[i] (they can never be a maximum again), then push i. From i = k - 1 on, record nums[front]. Each index is pushed and popped at most once, so the whole pass is linear.

Time

O(n)

Space

O(k)

Pitfall

Store indices in the deque, not values. With values alone you can't tell when the front has left the window. Also start recording only once i reaches k - 1, or you emit maximums of partial windows.

Solutions

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

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # indices, values decreasing front to back
        result = []
        for i, x in enumerate(nums):
            if dq and dq[0] <= i - k:
                dq.popleft()
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result