Sliding Window Maximum: monotonic deque

• Sliding Window Maximum – return the maximum value in each contiguous window of size K as it slides across an array.
• Monotonic deque – a double-ended queue of indices maintained so the values they point to decrease from front to back.
• Three operations per element – pop smaller values from back, push the new index, evict expired front.
• Linear time – each index is pushed once and popped at most once, giving O(n) total.
• O(K) space – the deque never holds more than K indices.

What is the Sliding Window Maximum problem?

Given an array of integers and a window size K, return an array containing the maximum of each contiguous window of K elements as the window slides from left to right. This is one of the most important hard-level problems and showcases the monotonic deque data structure.

package com.bank.service;

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

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. Pop smaller values from back
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            // 2. Push current index
            deque.offerLast(i);
            // 3. Evict expired front
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            // 4. Record once window is full
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] prices = {13, 8, 15, 10, 18, 6, 12};
        int k = 3;
        int[] peaks = maxSlidingWindow(prices, k);
        System.out.print("Window peaks: ");
        for (int p : peaks) System.out.print(p + " ");
    }
}

Window peaks: 15 15 18 18 18

Why does the naive approach fail for large inputs?

The naive approach scans each window for its maximum, giving O(K) work per window and O(n*K) total. For large arrays with large K, this is too slow. A heap improves to O(n log K) but the monotonic deque achieves true O(n).

// Naive: O(n*K)
for (int i = 0; i <= n - k; i++) {
    int max = Integer.MIN_VALUE;
    for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
    result[i] = max;
}
// For n=10^6, k=10^5: 10^11 operations -> too slow

Why store indices instead of values?

Evicting the front depends on knowing whether an element has slid out of the window. That requires comparing the element's index with the window boundary (i - k). Storing values alone gives no position information.

// Front eviction needs the index:
if (deque.peekFirst() <= i - k) deque.pollFirst();
// If deque stored values, this comparison would be meaningless

How does the decreasing invariant guarantee correctness?

• The back-eviction step removes every index whose value is less than or equal to the new value. After this, the deque's values are strictly decreasing from front to back. The front is always the largest value in the current window because:
• Any value larger than the front would have evicted the front when it entered.
• Any smaller value was either already evicted or sits behind the front.

// Invariant: deque values are decreasing front-to-back
// Example: deque indices [2, 5, 6], values [15, 10, 8]
// nums[2]=15 > nums[5]=10 > nums[6]=8
// Front (index 2, value 15) is the window maximum

How is this different from a heap-based approach?

| Approach | Time | Space | Removal |
|---|---|---|---|
| Naive | O(n*K) | O(1) | N/A |
| Max-heap | O(n log K) | O(K) | Lazy or O(K) per removal |
| Monotonic deque | O(n) | O(K) | Amortized O(1) per element |

// Heap approach: O(n log K)
// PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> b[0]-a[0]);
// For each element: add to heap, lazily remove expired, peek for max
// Each heap operation is O(log K)

What about using <= vs < for back eviction?

Using <= means equal-valued elements are also evicted. This is correct: if two elements have the same value, the newer one is better because it stays in the window longer. Using strict < would leave stale equal-valued indices that serve no purpose.

// CORRECT: use <= to evict equal values
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
    deque.pollLast();
}

// WRONG for efficiency: using < leaves equal-valued older indices
// They are useless because the newer equal value will outlast them

What are the edge cases?

A window of size 1 returns the original array. A window equal to the array length returns a single-element result (the global maximum). An empty array or null returns an empty result.

package com.bank.service;

public class SlidingMaxEdge {
    public static void main(String[] args) {
        int[] r1 = SlidingWindowMax.maxSlidingWindow(new int[]{5, 3, 7}, 1);
        for (int v : r1) System.out.print(v + " "); // 5 3 7
        System.out.println();

        int[] r2 = SlidingWindowMax.maxSlidingWindow(new int[]{5, 3, 7}, 3);
        for (int v : r2) System.out.print(v + " "); // 7
    }
}

5 3 7
7

What are common mistakes?

The most common mistake is forgetting the front eviction, which reports a maximum from outside the current window.

// WRONG: no front eviction
deque.offerLast(i);
// Missing: if (deque.peekFirst() <= i - k) deque.pollFirst();
// The front may point to an expired index

// CORRECT: always check front eviction after pushing
deque.offerLast(i);
if (deque.peekFirst() <= i - k) deque.pollFirst();

How do you adapt this for Sliding Window Minimum?

For the minimum instead of the maximum, keep the deque in increasing order. Pop from the back when the value is greater than or equal to the new value. Everything else stays the same.

// Sliding Window Minimum: increasing deque
while (!deque.isEmpty() && nums[deque.peekLast()] >= nums[i]) {
    deque.pollLast();
}
// Front is the minimum instead of the maximum

When should you use a monotonic deque?

Use a monotonic deque whenever you need the maximum (or minimum) of a sliding window in O(n) time. In banking, this applies to tracking rolling peak transaction rates, peak account balances, or minimum spreads over a time window.

package com.bank.service;

public class TrailingStopAlert {
    public static void main(String[] args) {
        int[] tickPrices = {100, 105, 103, 110, 108, 112, 107};
        int windowSize = 3;
        int[] peaks = SlidingWindowMax.maxSlidingWindow(tickPrices, windowSize);
        System.out.print("Rolling peaks: ");
        for (int p : peaks) System.out.print(p + " ");
    }
}

Rolling peaks: 105 110 110 112 112

What should a senior engineer know?

A senior engineer should explain the amortized O(n) proof: each of the n indices is pushed once and popped at most once, giving at most 2n deque operations. The deque never holds more than K indices. The invariant guarantees correctness, and the back-eviction with <= handles equal values correctly.

What are common interview follow-up questions?

• Interviewers commonly ask:
• Why indices, not values? (Front eviction depends on position.)
• Why <=? (Equal-valued older elements are useless.)
• Time complexity proof? (Each index pushed and popped at most once = O(n).)
• How about minimum instead of maximum? (Keep increasing order.)