Free lesson · DSA Mastery - Interview Prep, End to End

Sliding Window Maximum

Medium7 min readdsaqueues

Sliding Window Maximum

Sliding Window Maximum is the canonical monotonic-deque problem - the one every other problem in this sub-group is a variation of. A fixed window of size k slides across the array, and you report the maximum in each position. The naive approach recomputes each window's max in O(k); a heap gets O(n log k); but a single monotonic decreasing deque of indices delivers O(n): the front is always the window maximum, expired fronts are evicted as the window moves, and dominated backs are evicted as new elements arrive. We present all three approaches to show the progression to the optimal deque.

The insight is the purest statement of the pattern: maintain a deque of indices whose values strictly decrease from front to back. The front is the current window's max. When you slide, drop the front if it has left the window, and before inserting a new element, drop every back element it dominates (since a newer, larger value makes them irrelevant forever).

The Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window - an array of the maximum of each window position.

Example 1:

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

Explanation:
Window [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5,
[-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Example 2:

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Approaches Overview

Brute force scans each window. The heap holds elements with lazy removal of expired ones. The monotonic deque keeps the window max at its front in amortized O(1) - the definitive solution.

Approach 1: Brute Force

The Idea

For each window starting position, scan its k elements for the max. O(nk).

Logic Flowchart

graph TD
    A["for each window start i (0 .. n-k)"] --> B["scan nums[i .. i+k-1] for max"]
    B --> C["append max to result"]
    C --> D{"more windows?"}
    D -->|Yes| A
    D -->|No| E["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute force. For each window position we scan its k elements for the maximum and append it. Scanning each window gives order n times k time.

Complexity

Time: O(nk). Space: O(1) beyond output. The deque does it in O(n).

Approach 2: Max-Heap With Lazy Removal

The Idea

Push (value, index) into a max-heap. For each window end, the heap's top is the largest value seen - but it may be expired, so pop tops whose index is outside [end-k+1, end] before recording. Each element is pushed once and lazily removed, giving O(n log n).

Logic Flowchart

graph TD
    A["max-heap of (value, index)"] --> B["for end = 0 .. n-1"]
    B --> C["push (nums[end], end)"]
    C --> D{"end >= k-1?"}
    D -->|Yes| E["pop tops with index < end-k+1"]
    E --> F["record heap top value"]
    D -->|No| G["window not full yet"]
    F --> H{"more?"}
    G --> H
    H -->|Yes| B
    H -->|No| I["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the heap approach. We push each value with its index into a max-heap, and before recording each window's maximum we lazily pop any top whose index has expired. Each element is pushed once, giving order n log n time.

Complexity

Time: O(n log n). Space: O(n) for the heap.

Approach 3: Monotonic Decreasing Deque - Optimal (Canonical)

The Idea

Keep a deque of indices whose values strictly decrease from front to back. For each index i:

• Evict expired front: if deque.front() <= i - k, it has left the window - remove it.
• Evict dominated backs: while nums[deque.back()] <= nums[i], remove the back - a newer, at-least-as-large value makes those obsolete.
• Push i to the back.
• Once the first window is complete (i >= k - 1), record nums[deque.front()] - the window maximum.

Each index enters and leaves the deque once, so the total work is O(n).

Logic Flowchart

graph TD
    A["deque of indices (values decreasing); result empty"] --> B["for i = 0 .. n-1"]
    B --> C{"front <= i - k?"}
    C -->|Yes| D["evict front (expired)"]
    C -->|No| E["proceed"]
    D --> E
    E --> F{"nums[back] <= nums[i]?"}
    F -->|Yes| G["evict back (dominated)"]
    G --> F
    F -->|No| H["push i to back"]
    H --> I{"i >= k-1?"}
    I -->|Yes| J["record nums[front]"]
    I -->|No| K["window not full"]
    J --> L{"more?"}
    K --> L
    L -->|Yes| B
    L -->|No| M["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style K fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style L fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style M fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the monotonic deque. For each index we evict the front if it has left the window, evict back indices whose values are dominated by the current value, then push the current index. Once the first window is complete, the front holds the window maximum, recorded each step.

Code

public static int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();   // indices, values decreasing front-to-back
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();   // expired front
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();  // dominated
        dq.offerLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];       // window max
    }
    return result;
}

// Usage:
// maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) -> [3,3,5,5,6,7]

This Java code keeps a deque of indices with decreasing values. For each index it evicts an expired front, evicts dominated back indices, and pushes the current index. Once each window is complete, the front index gives the window maximum.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [1,3,-1,-3,5,3,6,7], k = 3:

graph LR
    F0["i0(1) dq[0]<br/>i1(3): 1<=3 evict; dq[1]<br/>i2(-1) dq[1,2]; window max nums[1]=3"]
    F1["i3(-3) dq[1,2,3]; front1<=0? no<br/>max nums[1]=3"]
    F2["i4(5): evict back 3,2; 1<=5 evict; front1<=1 expired evict; dq[4]<br/>max 5"]
    F3["i5(3) dq[4,5] max nums[4]=5<br/>i6(6): evict 5,4; dq[6] max 6"]
    F4["i7(7): evict 6; dq[7] max 7<br/>result [3,3,5,5,6,7]"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough slides a window of three over one, three, minus one, minus three, five, three, six, seven. The deque front always holds the window maximum: three, three, then five twice as the five dominates, then six and seven as each new peak arrives. The result is three, three, five, five, six, seven.

Result: [3, 3, 5, 5, 6, 7].

Complexity

Time: O(n) - each index enters and leaves the deque once. Space: O(k) - the deque holds at most one window of indices.

Complexity Comparison

The monotonic deque is the definitive solution and the archetype of the entire sub-group. Its two-sided eviction - expired by position at the front, dominated by value at the back - is the exact machinery the other window-extreme problems reuse.

Variations & Follow-ups

Why is the front always the window maximum?

The deque is kept strictly decreasing front-to-back, and expired indices are evicted from the front. So the front is the largest value among indices still inside the window - by definition the window maximum.

Why evict dominated backs?

If nums[i] >= nums[back] and i is newer, then back can never be a future window's max while i is present (any window containing back also contains the larger, longer-lived i). So back is obsolete and removed - this keeps the deque monotonic and bounded by k.

How do you get the sliding window minimum?

Flip the comparison: keep an increasing deque (evict backs that are >= the new value), and the front is the window minimum. The two combined are exactly the dual-deque setup from the previous two problems.

What about edge cases?

• k = 1: Every element is its own window max → the array itself.
• k = n: One window; the global max.
• Monotonic increasing input: Each new element dominates all; deque holds one element, front updates each step.
• Monotonic decreasing input: Nothing is dominated; the deque fills and the front expires as the window slides.

Common Interview Pitfalls

• Storing values instead of indices. You need indices to detect front expiry (front <= i - k).
• Evicting the front by value. Front eviction is by position (window expiry); back eviction is by value (domination).
• Recording before the window is full. Only record once i >= k - 1.
• Using < vs <= inconsistently on back eviction. <= discards equal stale values too, keeping the deque tight; either works for correctness but be consistent.

Why This Problem Matters

Sliding Window Maximum is the canonical monotonic-deque problem - the cleanest statement of "maintain a window extreme in amortized O(1)." Every other problem in this sub-group (Jump Game VI, the dual-deque spread problems, and the ones ahead) is a re-skinning of this exact two-sided-eviction deque. Master it and the rest are recognition exercises.

The next topic, Max Value of Equation, applies the deque to a 2D-flavored optimization: given points sorted by x, maximize y_i + y_j + |x_i - x_j| subject to |x_i - x_j| <= k. Rewriting the objective turns it into a sliding-window maximum over y - x, which a monotonic deque maintains directly - a great example of algebraic reframing exposing the window-max structure.

Back to DSA Mastery - Interview Prep, End to End