Sliding Window Max Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Stacks & Queues

Deque maintains candidates; amortized O(1) per element.

Concept

Sliding Window Maximum asks a deceptively simple question: given an array and a window size K, return the maximum value inside each window as the window slides across the array. The brute force is O(N*K) because each window rescans K values. A sort or a heap improves it to O(N log K) but still pays log factors at every step. The clean solution is O(N) using a monotonic deque of indices. The trick is that you never need to remember values that can never again become the max while still inside the current window, so you proactively evict them the moment they are dominated. This algorithm generalizes to any associative operation that supports a constant-time comparison, and it underlies real systems like streaming max aggregates over time-bounded windows and sliding-window rate limits that track peak usage.

Sliding Window Max — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Sliding Window Max visualization — animated algorithm, step-through, and live data-structure updates.

How it works

Use an ArrayDeque of indices, not values, and maintain two invariants. First, the values at those indices are strictly decreasing from front to back, so the front is always the max of the current window. Second, every index in the deque is inside the current window, meaning its distance from the current index i is less than K. At each new index i, first evict the front if it has slid out of the window, which is when deque.peekFirst() == i - k. Then evict from the back while the value at the back index is less than or equal to arr[i], because those older, smaller values cannot be the max while arr[i] is in scope. Then offer i to the back. Once i is at least k - 1, the window is fully formed and you record arr[deque.peekFirst()] as the answer for that window. Every index is offered and polled at most once, so the total work is O(N) even though the inner while loop is nested. The deque never holds more than K elements, so auxiliary space is O(K).

Implementation

maxSlidingWindow with ArrayDeque of indices

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMax {
    /**
     * Return the max of every contiguous window of size k in arr.
     * The deque holds indices whose values are strictly decreasing front-to-back.
     * O(N) time because each index is enqueued and dequeued at most once.
     */
    public static int[] maxSlidingWindow(int[] arr, int k) {
        if (arr == null || k <= 0 || arr.length < k) return new int[0];
        int n = arr.length;
        int[] out = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1) Evict indices that have slid out of the window.
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // 2) Maintain decreasing order: pop anything smaller than or equal to arr[i].
            while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) {
                dq.pollLast();
            }
            // 3) Append current index.
            dq.offerLast(i);

            // 4) Once the first full window is built, record the answer.
            if (i >= k - 1) {
                out[i - k + 1] = arr[dq.peekFirst()];
            }
        }
        return out;
    }

    /** Same algorithm adapted for streaming: feed one value at a time. */
    public static final class StreamingMax {
        private final int k;
        private final Deque<long[]> dq = new ArrayDeque<>(); // [index, value]
        private long index = 0;
        public StreamingMax(int k) { this.k = k; }
        public long offer(long v) {
            while (!dq.isEmpty() && dq.peekFirst()[0] <= index - k) dq.pollFirst();
            while (!dq.isEmpty() && dq.peekLast()[1] <= v) dq.pollLast();
            dq.offerLast(new long[]{index, v});
            index++;
            return dq.peekFirst()[1];
        }
    }
}

Complexity

Time: O(N), each index enters and leaves the deque at most once
Space: O(K), the deque is bounded by the window width

Common pitfalls

Storing values in the deque instead of indices, losing the ability to evict stale entries
Using < vs <= when popping from the back changes how duplicates are handled; for max, <= is safe
Forgetting to evict stale indices from the front, which yields values from outside the window
Recording an answer before the first full window is formed (i < k - 1)
Allocating a new deque per window instead of reusing one across the whole iteration
Using java.util.Stack or LinkedList; ArrayDeque is materially faster

Key design decisions & trade-offs

Algorithm — Chosen: Monotonic deque. O(N) beats O(N log K) of heap or O(N*K) of brute force, and code is still short
Deque implementation — Chosen: ArrayDeque. Backed by a circular array, no per-op allocation, no synchronization overhead
Evict condition — Chosen: Pop back while back <= current. Using <= keeps the deque as small as possible and still returns correct max

Practice problems

Sliding Window Maximum

Interview follow-ups

Sliding Window Minimum (same code with flipped comparator)
First Negative Number in every window of size K
Sliding window median (needs two heaps or a balanced BST)
Longest subarray where max - min <= limit
Streaming peak usage for a sliding time-based rate limiter

Why it matters

Sliding Window Max is a core part of the Stacks & Queues toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".