Sliding Window Maximum

Concept Overview

The sliding window maximum problem asks us to find the maximum element in each contiguous subsegment of size k within a sequence of length n. A naive approach takes O(n * k) time by scanning each window, but we can optimize this to O(n) using a monotone deque (double-ended queue). The deque maintains a sequence of useful indices, dropping elements that are out of bounds or strictly smaller than the newly considered element.

Algorithm Details

The monotone deque strictly maintains the indices of potential maximum candidates for the current and upcoming windows. When examining element at index i:

Expire: Remove indices from the front of the deque that are outside the current window bounds (i.e., index <= i - k).
Dominate: Remove indices from the back of the deque that correspond to elements strictly smaller than the current element. They can never be the maximum because the new, larger element will outlast them.
Append: Add the current index i to the back of the deque. Equal values are retained, meaning the earliest index wins when returning the maximum.

After processing each element, if the window has reached its full size (i >= k - 1), the maximum for the window is the element at the index stored at the front of the deque.

Worked Example

Let's evaluate a sequence of numbers: 2, -1, 4, 4, 0 with a window size of k = 3.

We process the elements step-by-step:

Index 0 (Value 2): The deque is empty. We append index 0. Deque: [0]. The window size is 1 (not complete).
Index 1 (Value -1): The value -1 is not strictly greater than 2, so we append index 1. Deque: [0, 1]. The window size is 2 (not complete).
Index 2 (Value 4): The value 4 is greater than -1 (index 1) and 2 (index 0). We pop both indices from the back and append index 2. Deque: [2]. The window is now size 3 (complete). Window maximum is 4 at index 2.
Index 3 (Value 4): The value 4 is not strictly greater than 4, so we retain index 2 and append index 3. Deque: [2, 3]. The window maximum is 4 at index 2.
Index 4 (Value 0): Index 2 remains in the window because 2 > 4 - 3 = 1. The value 0 is not greater than 4, so we append index 4. Deque: [2, 3, 4]. The window maximum is 4 at index 2.

The final window maxima are [4, 4, 4] with argmax indices [2, 2, 2] and complete window count 3.

Experimenting with the Module

You can interact with the monotone deque behavior by using the Sliding Window Maximum module.

Enter 2,-1,4,4,0 in Sequence and select 3 in Window k.
Use the Step button to advance element by element, observing how the deque evicts smaller values and expires old indices.
Notice how multiple equal maximums are resolved by keeping earlier indices at the front of the deque.

Limitations

The visualizer processes at most12 integers. The core deque advances a head index rather than shifting its array. Saved teaching snapshots copy the current deque/output arrays and use quadratic storage in this bounded trace; that cost is separate from the linear core scan. In practice, the linear time algorithm efficiently processes streams or arrays containing millions of entries. Furthermore, the model handles basic integer elements; applications using composite elements (like timestamped records) may require customized comparator operations.

References

The formulation of the sliding window maximum problem allows for an elegant reduction from O(n * k) to amortized O(n) running time.

CP-Algorithms: Indexed monotone queue and all fixed-length subarray minima

Sliding Window Maximum