Sliding Window Maximum

Hard Problem 27 of 151 Java and Python

Problem

You are given an integer array nums and a window of size k that slides from the very left of the array to the very right, one position at a time.

Return an array with the maximum value of each window.

Example 1

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Why: Windows: [1 3 -1] → 3, [3 -1 -3] → 3, [-1 -3 5] → 5, and so on.

Example 2

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

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ k ≤ nums.length

Explanation

Once a bigger number enters the window, every smaller number before it can never be a maximum again: it will leave the window first.

So keep a deque of indices whose values decrease from front to back. The front is the current maximum. Drop indices from the back that are smaller than the new value, and from the front once they slide out of the window.

Approach 1 · Naive

Scan each window

Time O(n · k)
Space O(1) besides the output

For every window, scan its k elements for the maximum.

For each start i from 0 to n – k, compute max(nums[i..i + k - 1]).

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i + k <= nums.length; i++) {
            int max = nums[i];
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

Python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

Approach 2 · Optimal

Monotonic deque

Time O(n), each index enters and leaves once
Space O(k)

Store indices in a deque with decreasing values. The front holds the index of the current window's maximum.

For each i: pop from the front if that index is i - k (it left the window).
Pop from the back while nums[back] <= nums[i]; then push i.
Once i >= k - 1, append nums[front] to the result.

Java

import java.util.*;

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

Python

from collections import deque

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

Complexity compared

Approach	Time	Space
Naive Scan each window	O(n · k)	O(1) besides the output
Optimal Monotonic deque	O(n), each index enters and leaves once	O(k)

Key takeaways

Store indices in the deque, not values, so you can tell when the front has left the window.
A max-heap with lazy deletion also works, in O(n log n).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem