javascript 28 lines · 7 steps

Sliding window maximum with a deque

A monotonic deque tracks the maximum of every fixed-size window in a single linear pass.

Explained by highlit
Advanced sliding-window monotonic-deque amortized-analysis arrays
1// Sliding window maximum using a monotonic decreasing deque.
2// Returns an array of the maximum value within each window of size k.
3function maxSlidingWindow(nums, k) {
4 const result = [];
5 const deque = []; // stores indices, values in decreasing order
6 
7 for (let i = 0; i < nums.length; i++) {
8 // Remove indices that have slid out of the window on the left.
9 if (deque.length && deque[0] <= i - k) {
10 deque.shift();
11 }
12 
13 // Maintain decreasing order: drop smaller values from the back,
14 // since they can never be the max while nums[i] is in the window.
15 while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
16 deque.pop();
17 }
18 
19 deque.push(i);
20 
21 // The front always holds the index of the current window's max.
22 if (i >= k - 1) {
23 result.push(nums[deque[0]]);
24 }
25 }
26 
27 return result;
28}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A monotonic deque keeps candidates ordered so the maximum is always at the front in O(1).
  2. 2Each index is pushed and popped at most once, giving an overall O(n) runtime despite the nested loop.
  3. 3Storing indices instead of values lets you detect when an element has slid out of the window.

Related explainers

javascript 
'use server'
 
import { revalidatePath } from 'next/cache'
import { redirect } from 'next/navigation'

How a Next.js Server Action updates a post

server-actions authorization validation
Intermediate 7 steps
javascript 
const express = require('express');
 
const v1 = express.Router();
 

Versioning an API with Express Routers

api versioning routing modularity
Intermediate 10 steps
java 
public class SortedListMerger {
 
    public static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];

Merging two sorted arrays in Java

two-pointers merging arrays
Beginner 6 steps
python 
import time
from collections import defaultdict
from threading import Lock
 

Sliding-window login rate limiting in Flask

rate-limiting sliding-window thread-safety
Intermediate 7 steps
javascript 
const RATE_LIMIT = 100;
const WINDOW_MS = 60 * 1000;
const BLOCK_MS = 5 * 60 * 1000;
 

Building a rate-limiting middleware in Express

rate-limiting middleware closures
Intermediate 9 steps
java 
import java.util.ArrayDeque;
import java.util.Deque;
 
public final class RollingAverage {

A rolling average over a sliding window

sliding-window running-sum deque
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Sliding window maximum with a deque — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code