Sliding Window Maximum

hardAmazon-tagged: Mixed64 stepsJava · Python · C++

Return the maximum of every window of size k. Keep a deque of indices whose values are decreasing. Before adding index i, pop smaller values from the back (they can never be a maximum again) and drop the front if it slid out of the window. The front is always the current maximum.

▶ Watch the animated trace

Traced input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]. Original problem: neetcode.io/problems/sliding-window-maximum

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(k)

Each index is pushed and popped at most once.

Key idea

A value smaller than a newer value is useless: the newer one outlives it and beats it.
So the deque stays decreasing from front to back.
Store indices to know when the front leaves the window.
Record nums[deque.front] once the first full window is formed.

Common mistakes

A max-heap works but is O(n log n) and needs lazy deletion.
Storing values instead of indices loses track of expiry.

Solution

Java

int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < nums.length; 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) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

Python

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    res, dq = [], deque()
    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: res.append(nums[dq[0]])
    return res

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;
    for (int i = 0; i < (int)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) res.push_back(nums[dq.front()]);
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
k = 1 Each window is a single element.	`nums = [4, 2, 7], k = 1`	`[4, 2, 7]`
k = n One window.	`nums = [1, 5, 2], k = 3`	`[5]`
Decreasing input Nothing gets popped from the back; the front expires each time.	`nums = [9, 8, 7, 6], k = 2`	`[9, 8, 7]`