Maximum of Every Sliding Window of Size K

Hard25–30 min

Topics

ArraySliding WindowDeque

Companies

AmazonGoogleMicrosoftAdobe

Given an array nums and an integer k, return an array where each value is the maximum of the window nums[i..i+k-1], for every valid window position as the window slides from the start of the array to the end. Recomputing the max of every window from scratch is correct but wasteful — most of a window's elements are shared with the window right before it. The fix is a deque that only ever holds candidates that could still become a future window's maximum, kept in strictly decreasing order of value. Because the front of a decreasing deque is always the biggest value currently in the window, reading the answer for each window becomes O(1), and every index is pushed and popped from the deque at most once — giving O(n) overall despite the nested-looking while loops inside the for.

Test Case 1:

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

Output:[3, 3, 5, 5, 6, 7]

Explanation:Every window of size 3, in order: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7.

Test Case 2:

Input:nums = [9, 11], k = 2

Output:[11]

Explanation:Only one window exists — the whole array.

Test Case 3:

Input:nums = [4, -2], k = 2

Output:[4]

Explanation:Only one window exists — the whole array.

Constraints

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-10 integers, -10 to 10k (window size) — 1 to nums.length

1	class Solution {
2	public int[] maxOfEverySlidingWindow(int[] nums, int k) {
3	Deque<Integer> deque = new ArrayDeque<>();
4	int[] result = new int[nums.length - k + 1];
5	for (int i = 0; i < nums.length; i++) {
6	while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
7	deque.pollFirst();
8	}
9	while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
10	deque.pollLast();
11	}
12	deque.offerLast(i);
13	if (i >= k - 1) {
14	result[i - k + 1] = nums[deque.peekFirst()];
15	}
16	}
17	return result;
18	}
19	}
20

Array

-1

-3

Queue

empty

INITIALIZE

Start with an empty deque of indices (front is always the current window's max) and an empty result array.

Step 1 / 10

Approach & Solutions

Brute Force

Brute

For every window start, scan all k elements to find the maximum and store it. Correct, but every window shares almost all of its elements with the window right before it — re-scanning from scratch every time throws that overlap away.

TimeO(n·k)

SpaceO(n-k+1)

Java

Try it out

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

Optimal — Monotonic Deque

Optimal

Keep a deque of indices whose values are in strictly decreasing order, so the front is always the max of the current window. At each index: drop any front index that has fallen out of the window, drop any back index whose value is smaller than the one just arrived (it can never be a future max), then push the new index. Once the window is full, the front is the answer — no re-scanning.

TimeO(n)

SpaceO(k)