Sliding Window Maximum

Master this topic with zero to advance depth.

Sliding Window Maximum

Given an array nums and a window size k, return the maximum in each sliding window.

Visual Representation

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

Window: [1, 3, -1]   Max: 3
Window: [3, -1, -3]  Max: 3
Window: [-1, -3, 5]  Max: 5

Monotonic Deque (indices):
Step 1 (1): [0]
Step 2 (3): [1] (discarded 0 since 3 > 1)
Step 3 (-1): [1, 2]
Step 4 (-3): [1, 2, 3]
Step 5 (5): [4] (discarded 1, 2, 3 since 5 is larger)

Hard

Examples

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

Approach 1

Level I: Brute Force

Intuition

For every possible sliding window of size k, iterate through all its elements to find the maximum value.

Thought Process

There are n - k + 1 windows in an array of size n.
For each window starting at index i, loop from i to i + k - 1 to find the max.
Store the result in an array.

⏱ O(N * K)💾 O(1) excluding the result array.

Detailed Dry Run

Window	Elements	Max	Result
[0, 2]	[1, 3, -1]	3	[3]
[1, 3]	[3, -1, -3]	3	[3, 3]
[2, 4]	[-1, -3, 5]	5	[3, 3, 5]

java

import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return new int[0];
        int[] res = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int max = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] > max) max = nums[j];
            }
            res[i] = max;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums, 3))); // [3, 3, 5, 5, 6, 7]
    }
}

Approach 2

Level II: Heaps / Priority Queue (O(N log N))

Intuition

To find the maximum in a window efficiently, we can use a Max-Heap (Priority Queue). The heap stores pairs of (value, index). For each window, we add the current element to the heap and then remove elements from the top of the heap if their indices are outside the current window.

Thought Process

Use a Max-Heap to store [nums[i], i].
In each step, add the current element to the heap.
Peek at the top of the heap. If the index is less than i - k + 1, it's outside the window; remove it (pop).
The top of the heap is the maximum for the current window.

Pattern: Sliding Window + Heap Optimization

⏱ O(N log N) - In the worst case, we push all $N$ elements into the heap.💾 O(N) - To store elements in the heap.

java

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            if (i >= k - 1) {
                while (pq.peek()[1] <= i - k) pq.poll();
                res[i - k + 1] = pq.peek()[0];
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Monotonic Deque)

Intuition

Thought Process

We need a way to find the maximum in the current window in $O(1)$ . A Monotonic Deque stores indices of elements in strictly decreasing order of their values (nums[dq.front()] is always max).

Logic Steps

Clean Deque (Old indices): If the index at the front is outside the current window [i-k+1, i], remove it.
Maintain Monotonicity: Before adding nums[i], remove all indices from the back whose values are $\le nums[i]$ . They can never be the maximum in any future window containing nums[i].
Add Result: Once the window reaches size k, the value at nums[dq.front()] is the maximum for the current window.

⏱ O(N) - Each index is pushed and popped at most once.💾 O(K) for the deque.

Detailed Dry Run

i	Val	Action	Deque (Indices)	Result
1	3	Pop 0 (1 < 3)	[1]	-
2	-1	Push 2	[1, 2]	[3]
3	-3	Push 3	[1, 2, 3]	[3, 3]
4	5	Pop all (all < 5)	[4]	[3, 3, 5]

java

import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 1. Remove indices outside current window
            if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
            // 2. Maintain monotonic decreasing property
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            // 3. Add current
            dq.offerLast(i);
            // 4. Record max
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums, 3)));
    }
}

⚠️ Common Pitfalls & Tips

Storing values instead of indices in the deque makes it hard to check if the maximum element has slid out of the window. Always store indices.

← Previous QuestionFind All Anagrams in a String

Next Question →Minimum Window Subsequence

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.