Double-Ended Queues and Monotonic Deque Invariants: Sliding Window Maximum

01The Problem of Sliding Window Extremes

Given an array nums and a sliding window of size k moving from left to right, we must find the maximum value in every window. A naive solution scans all k elements for each of the (n - k + 1) window positions, resulting in O(n * k) runtime.

Using a PriorityQueue (Max-Heap) allows finding the maximum in O(1) and adding elements in O(log k). However, removing an element that leaves the window requires O(k) linear removal from the heap (or O(log k) with lazy deletion), resulting in O(n log k) overall time.

To achieve true amortized O(n) linear time, we utilize a Monotonic Double-Ended Queue (Deque). A monotonic deque stores elements in strictly descending order, guaranteeing that the maximum element of the current window is always at the front of the deque.

02The Domination Principle Explained

Why is it safe to discard smaller elements from the back of the deque? Consider two elements: nums[a] and nums[b], where a < b and nums[a] <= nums[b].

Because index b is newer than index a, nums[b] will remain in the sliding window longer than nums[a]. And because nums[b] is larger than or equal to nums[a], nums[a] can NEVER be the maximum in any current or future window that contains nums[b]!

Element nums[a] is completely dominated. Discarding it immediately maintains a strictly decreasing sequence in the deque, ensuring that peekFirst() always returns the window maximum.

03Step-by-Step Monotonic Deque Trace Table

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

+---+---------+-----------------------+-------------------+---------------+| i | nums[i] | Deque Indices (Values)| Action Taken      | Result Output |+---+---------+-----------------------+-------------------+---------------+| 0 | 1       | [0 (1)]               | Pushed 0          | -             || 1 | 3       | [1 (3)]               | 1 popped (1 < 3)  | -             || 2 | -1      | [1 (3), 2 (-1)]       | Pushed 2          | 3 (Window 1)  || 3 | -3      | [1 (3), 2 (-1), 3 (-3)| Pushed 3          | 3 (Window 2)  || 4 | 5       | [4 (5)]               | All popped (5 >)  | 5 (Window 3)  || 5 | 3       | [4 (5), 5 (3)]        | Pushed 5          | 5 (Window 4)  || 6 | 6       | [6 (6)]               | All popped (6 >)  | 6 (Window 5)  || 7 | 7       | [7 (7)]               | All popped (7 >)  | 7 (Window 6)  |+---+---------+-----------------------+-------------------+---------------+Final Output Array: [3, 3, 5, 5, 6, 7]

04Amortized Complexity Analysis

Although the inner while loops appear to introduce nested iteration, each element index from 0 to n - 1 is pushed onto the deque exactly once and popped from the deque at most once.

Therefore, across the entire execution of the algorithm, at most 2n deque operations occur. The total amortized runtime is strictly O(n), and the auxiliary space is bounded by the window size O(k).

05Production Architecture & Engineering Trade-Offs

When selecting data structures for high-concurrency environments, developers must analyze both time complexity and memory overhead. Standard collection classes wrap primitive values in heap-allocated wrapper objects, introducing substantial pointer overhead and degrading CPU cache locality. In high-frequency messaging pipelines, storing millions of boxed integers in an ArrayList creates gigabytes of object overhead that stresses garbage collection cycles.

To achieve predictable low-latency throughput, production systems favor primitive-specialized collections or contiguous off-heap direct buffers. Additionally, when using ConcurrentHashMap, choosing the appropriate initial capacity and load factor avoids expensive table rehashing and concurrent bucket redistribution during peak transaction surges.