Sliding Window Maximum | Monotonic Deque

Problem Statement

Given an array nums and an integer k, return the maximum element for every sliding window of size k.

Brute Force Intuition

In an interview, you can explain it like this:

For every window of size k, iterate through all its elements and find the maximum.

Since every window is scanned completely, many elements are processed repeatedly.

Complexity

• Time Complexity: O(N × K)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;

        int[] ans = new int[n - k + 1];

        int index = 0;

        for (int i = 0; i <= n - k; i++) {

            int max = nums[i];

            for (int j = i; j < i + k; j++) {

                max = Math.max(max, nums[j]);
            }

            ans[index++] = max;
        }

        return ans;
    }
}

Moving Towards the Optimal Approach

Notice that while moving the window:

One element leaves

One element enters

Do we really need to calculate the maximum again?

No.

We only need to keep the useful candidates that can become the maximum.

This is where a Monotonic Deque comes in.

Pattern Recognition

Whenever you see:

• Sliding Window
• Maximum / Minimum in every window
• Fixed Window Size

Think:

Monotonic Deque

Key Observation

Maintain indices in a deque such that:

Elements remain in decreasing order.

Then:

Front of deque

=

Maximum of current window

Whenever a new element comes:

Remove all smaller elements from the back.

They can never become the maximum.

Optimal Approach

For every index:

Step 1

Remove indices outside the window.

deque.peekFirst() <= i - k

Step 2

Remove smaller elements from the back.

nums[deque.peekLast()] <= nums[i]

Step 3

Insert current index.

Step 4

Once window size becomes k:

Front of deque
=
Maximum

Optimal Java Solution

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;

        int[] ans = new int[n - k + 1];

        Deque<Integer> dq = new ArrayDeque<>();

        int index = 0;

        for (int i = 0; i < n; i++) {

            while (!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) {

                ans[index++] = nums[dq.peekFirst()];
            }
        }

        return ans;
    }
}

Dry Run

Input

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

k = 3

Window

[1 3 -1]

Deque:

3

Maximum:

3

Window

[3 -1 -3]

Maximum:

3

Window

[-1 -3 5]

Remove:

-3

-1

Deque:

5

Maximum:

5

Continue similarly.

Final Answer:

[3,3,5,5,6,7]

Why Monotonic Deque Works?

Every index:

Inserted once

Removed once

So each element is processed only one time.

The deque always maintains candidates in decreasing order.

The front always stores the maximum element of the current window.

Complexity Analysis

Interview One-Liner

Maintain a monotonic decreasing deque of indices so the front always represents the maximum element of the current sliding window.

Pattern Learned

Sliding Window

+

Maximum / Minimum

↓

Monotonic Deque

Similar Problems

• Sliding Window Maximum
• Sliding Window Minimum
• First Negative Integer in Every Window
• Shortest Subarray with Sum at Least K
• Constrained Subsequence Sum

Memory Trick

Think:

New Element Arrives

↓

Remove Smaller Elements

↓

Insert Current Index

↓

Front = Maximum

Mental Model

Sliding Window

↓

Useful Candidates Only

↓

Deque

↓

Front Always Maximum

Whenever you hear:

"Maximum in every sliding window"

your brain should immediately think:

Monotonic Deque