Sliding Window Maximum

Problem Statement

Given an integer array nums and a window size k, slide a window of size k from left to right across the array. For each window position, report the maximum element inside the window.

Example

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

Window position                Max
---------------------------------
[1  3  -1] -3  5  3  6  7      3
 1 [3  -1  -3] 5  3  6  7      3
 1  3 [-1  -3  5] 3  6  7      5
 1  3  -1 [-3  5  3] 6  7      5
 1  3  -1  -3 [5  3  6] 7      6
 1  3  -1  -3  5 [3  6  7]     7

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

Constraints

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

The output array has length n - k + 1.

Approach 1: Brute Force — O(n·k)

For each of the n - k + 1 window positions, scan all k elements to find the maximum.

int[] maxSlidingWindowBrute(int[] nums, int k) {
    int n = nums.length;
    int[] result = 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++) {
            max = Math.max(max, nums[j]);
        }
        result[i] = max;
    }
    return result;
}

Time: $O(n \cdot k)$. Space: $O(1)$ beyond the output array. Acceptable when k is small, but degrades badly when k approaches n.

Approach 2: Max-Heap — O(n log n)

A max-heap (priority queue) keeps track of elements in the current window. The heap’s root always holds the largest value. The challenge: Java’s PriorityQueue does not support efficient removal of arbitrary elements by index.

Lazy Deletion Strategy

Store (value, index) pairs in the heap. When the root’s index falls outside the current window, pop it. This “lazy deletion” defers removal until the stale element surfaces at the top.

int[] maxSlidingWindowHeap(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];

    // Max-heap ordered by value (descending), then by index (descending)
    PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]
    );

    for (int i = 0; i < n; i++) {
        heap.offer(new int[]{nums[i], i});

        // Evict stale entries whose index is outside the window
        while (heap.peek()[1] < i - k + 1) {
            heap.poll();
        }

        if (i >= k - 1) {
            result[i - k + 1] = heap.peek()[0];
        }
    }
    return result;
}

Time: $O(n \log n)$ worst case. Each of the n elements is inserted once ($O(\log n)$) and removed at most once ($O(\log n)$). In practice, lazy deletion means the heap can temporarily hold more than k elements.

Space: $O(n)$ in the worst case (all elements remain in the heap until they are lazily evicted).

This approach improves over brute force but falls short of optimal.

Approach 3: Monotonic Deque — O(n) Time, O(k) Space

What is a Monotonic Deque?

A monotonic deque (double-ended queue) maintains its elements in a strict monotonic order—either always increasing or always decreasing from front to back. Elements that violate the ordering invariant are removed before a new element enters.

For the sliding window maximum, use a decreasing monotonic deque: the front of the deque holds the index of the current window’s maximum value, and every subsequent index in the deque has a strictly smaller corresponding value.

Why It Works

A value nums[j] can never be the window maximum while a larger or equal value nums[i] (where i > j) exists in the same window. Once nums[i] enters, nums[j] is permanently dominated—it will never be the answer for this window or any future window. Removing nums[j] from the deque is safe and keeps the structure lean.

How It Works — Step by Step

Maintain a deque that stores indices (not values). For each new element nums[i]:

1. Purge dominated entries from the back. While the deque is non-empty and nums[deque.peekLast()] ≤ nums[i], remove the back element. These elements are smaller than the newcomer and will never be a future maximum.
2. Add the new index to the back. Push i onto the deque.
3. Evict expired entries from the front. If deque.peekFirst() < i - k + 1, the front element has slid out of the window. Remove it.
4. Record the answer. Once the window is full (i ≥ k - 1), nums[deque.peekFirst()] is the maximum for this window.

Visual Walkthrough

Trace the algorithm with nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3.

The deque stores indices. The notation [idx₁, idx₂, ...] shows the deque from front to back, with the corresponding values annotated.

i=0  nums[0]=1
     Deque: [0]          → values: [1]
     Window not full yet.

i=1  nums[1]=3
     Back purge: nums[0]=1 ≤ 3 → remove 0
     Deque: [1]          → values: [3]
     Window not full yet.

i=2  nums[2]=-1
     Back purge: nums[1]=3 > -1 → stop
     Deque: [1, 2]       → values: [3, -1]
     Window full → answer = nums[1] = 3

i=3  nums[3]=-3
     Back purge: nums[2]=-1 > -3 → stop
     Deque: [1, 2, 3]    → values: [3, -1, -3]
     Front check: 1 ≥ 3-3+1=1 → keep
     Window full → answer = nums[1] = 3

i=4  nums[4]=5
     Back purge: nums[3]=-3 ≤ 5 → remove 3
                 nums[2]=-1 ≤ 5 → remove 2
                 nums[1]=3  ≤ 5 → remove 1
     Deque: [4]          → values: [5]
     Window full → answer = nums[4] = 5

i=5  nums[5]=3
     Back purge: nums[4]=5 > 3 → stop
     Deque: [4, 5]       → values: [5, 3]
     Window full → answer = nums[4] = 5

i=6  nums[6]=6
     Back purge: nums[5]=3 ≤ 6 → remove 5
                 nums[4]=5 ≤ 6 → remove 4
     Deque: [6]          → values: [6]
     Window full → answer = nums[6] = 6

i=7  nums[7]=7
     Back purge: nums[6]=6 ≤ 7 → remove 6
     Deque: [7]          → values: [7]
     Window full → answer = nums[7] = 7

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

Notice how the deque never holds more than k elements, and at step i=4 three elements are purged at once—demonstrating the amortized cost.

Implementation

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

final class SlidingWindowMaximum {

    int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();  // stores indices

        for (int i = 0; i < n; i++) {
            // 1. Remove indices whose values are ≤ current value
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            // 2. Add current index
            deque.offerLast(i);

            // 3. Remove front if outside the window
            if (deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 4. Record the window maximum
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

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

Why O(n)?

Each element enters the deque exactly once (via offerLast) and leaves the deque at most once (via pollLast or pollFirst). Across all n iterations, the total number of deque operations is at most 2n.

Amortized argument using the aggregate method:

• Let $T_{\text{insert}}$ = total insert operations = $n$
• Let $T_{\text{remove}}$ = total remove operations ≤ $n$ (each element removed at most once)
• Total work = $T_{\text{insert}} + T_{\text{remove}} \leq 2n$
• Amortized cost per element = $\frac{2n}{n} = O(1)$

The key insight: although a single iteration can remove multiple elements from the back (as seen at i=4 above), each of those elements was added exactly once in a prior iteration. The removal cost is “prepaid” by the insertion.

Complexity Comparison

Approach	Time	Space	Notes
Brute Force	$O(n \cdot k)$	$O(1)$	Scans each window linearly
Max-Heap	$O(n \log n)$	$O(n)$	Lazy deletion causes heap bloat
Monotonic Deque	$O(n)$	$O(k)$	Optimal; each element enters and exits once

The Monotonic Deque Pattern

The monotonic deque is not a single-problem trick—it recurs across a family of problems that share the same structural requirement: efficiently query the extremum within a sliding range.

Pattern Template

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

/**
 * Monotonic deque template.
 * Maintains indices in the deque such that corresponding values
 * are in decreasing order (for max queries) or increasing order
 * (for min queries).
 *
 * @param nums       the input array
 * @param k          the window size
 * @param findMax    true for maximum, false for minimum
 * @return           array of extremums for each window position
 */
static int[] slidingWindowExtremum(int[] nums, int k, boolean findMax) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // Purge dominated entries based on direction
        while (!deque.isEmpty() &&
               (findMax ? nums[deque.peekLast()] <= nums[i]
                        : nums[deque.peekLast()] >= nums[i])) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // Evict expired front
        if (deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Problems That Use This Pattern

Problem	Variation
Sliding Window Minimum	Use an increasing monotonic deque instead of decreasing.
Stock Span Problem	For each day, find how many consecutive previous days had a price ≤ today’s price. Monotonic stack (a deque used only from one end).
Next Greater Element	For each element, find the nearest element to the right that is larger. Classic monotonic stack application.
Shortest Subarray with Sum ≥ K	Combine prefix sums with a monotonic deque to find the shortest subarray whose sum meets the threshold.
Jump Game VI	DP with monotonic deque: dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Exact sliding window maximum structure.
Constrained Subsequence Sum	Same DP-with-deque structure as Jump Game VI.

Recognizing the monotonic deque pattern transforms an $O(n \cdot k)$ brute-force DP into an $O(n)$ solution.

Edge Cases

Case	Expected Behavior
k = 1	Every element is its own window maximum; return the input array unchanged.
k = nums.length	Single window; return one element—the global maximum.
All elements equal, e.g., [4, 4, 4, 4]	Every window maximum is 4. Deque grows to size k since no element dominates another.
Sorted ascending, e.g., [1, 2, 3, 4, 5]	The deque holds at most one element at any time (each new element purges all previous ones).
Sorted descending, e.g., [5, 4, 3, 2, 1]	The deque grows to size k since no new element dominates the existing ones. Front eviction triggers at every step once the window is full.
Array with negative numbers	The algorithm handles negative values correctly—comparisons work identically regardless of sign.
k equals 1 and array has one element	Returns [nums[0]].

Implementation Variant: Circular Buffer

For extremely large arrays where the deque’s internal resizing overhead matters, a fixed-size circular buffer provides tighter memory control.

final class CircularBufferSlidingMax {

    int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];

        // Circular buffer storing indices; capacity k+1 handles wrap-around
        int[] buf = new int[k + 1];
        int front = 0, back = 0;

        for (int i = 0; i < n; i++) {
            // Purge dominated entries from the back
            while (front != back && nums[buf[(back - 1 + buf.length) % buf.length]] <= nums[i]) {
                back = (back - 1 + buf.length) % buf.length;
            }

            // Add current index
            buf[back] = i;
            back = (back + 1) % buf.length;

            // Evict expired front
            if (buf[front] < i - k + 1) {
                front = (front + 1) % buf.length;
            }

            if (i >= k - 1) {
                result[i - k + 1] = nums[buf[front]];
            }
        }
        return result;
    }
}

This version allocates exactly k + 1 slots and avoids ArrayDeque’s dynamic resizing. The performance difference is negligible for most interview scenarios, but worth mentioning for system-level discussions.

Interviewer Tips

How to explain the invariant: Start with a clear one-sentence statement—“The front of the deque always holds the index of the current window’s maximum.” Build from there by explaining the two maintenance operations (back purge and front eviction).

The amortized O(n) proof matters. Interviewers frequently ask why the algorithm is $O(n)$ despite the inner while loop. The answer: each element is added once and removed at most once, giving $2n$ total operations. Practice delivering this explanation in under 30 seconds.

Draw the deque at each step. A visual trace like the one above demonstrates understanding far more effectively than code alone. Use the example array and show four or five steps.

Common mistake to flag: storing values in the deque instead of indices. Without indices, there is no way to check whether the front element has slid out of the window. Always store indices and look up values via nums[deque.peekFirst()].

Follow-up questions interviewers ask:

• “How would you compute the sliding window median?” — Use two heaps (max-heap for the lower half, min-heap for the upper half) with lazy deletion, achieving $O(n \log k)$ time.
• “What if the window size changes dynamically?” — A balanced BST or order-statistics tree (like Java’s TreeMap with frequency tracking) supports insertion, deletion, and max queries in $O(\log k)$ per operation.
• “Can you do this in parallel?” — Divide the array into blocks of size k. Compute prefix and suffix maximums for each block in $O(n)$ total, then combine them for each window in $O(1)$. This approach (called the “sparse table” or “block decomposition” method) also runs in $O(n)$ but is more parallelizable.