Queue • Sliding Window

Sliding Window Maximum

Given an array and a sliding window of size K, find the maximum element in the window at each step. This is the classic problem that proves the immense power of the Deque (Double Ended Queue).

Try Interactive Simulator

The Naive Approach

Scanning all K elements for every shift takes O(N*K) time. For large windows, this is brutally slow.

Monotonic Deque

We use a Deque to store indices. We maintain it such that the values it points to are strictly decreasing. This guarantees the absolute maximum for the current window is always at the `front`.

Two Exits

Elements leave the Deque for two reasons: (1) from the back, because a larger element came in and rendered them permanently useless. (2) from the front, because the window simply slid past their index.

1

3

-1

-3

5

3

Deque (Stores Indices)

Empty

← Front (Max)Back →

Result Array

Code Tracker

:::

1let deque = []; let res = [];

2for (let i = 0; i < nums.length; i++) {

3 if (deque.length && deque[0] === i - k) {

4 deque.shift();

5 }

6 while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {

7 deque.pop();

8 }

9 deque.push(i);

10 if (i >= k - 1) {

11 res.push(nums[deque[0]]);

12 }

13}

14return res;