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

php 
<?php
 
class NameParser
{

Parsing a full name into components in PHP

string-parsing arrays normalization
Intermediate 8 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
javascript 
import { useState, useEffect, useCallback, useRef } from 'react';
 
const cache = new Map();
const inflight = new Map();

Building a stale-while-revalidate hook in React

caching request-deduplication custom-hooks
Advanced 10 steps
javascript 
import { useEffect, useRef, useState } from 'react';
 
export function useDelayedFlag(active, delay = 300) {
  const [visible, setVisible] = useState(false);

Delaying a loading spinner with a React hook

custom-hooks debouncing cleanup
Intermediate 8 steps
javascript 
const SWIPE_THRESHOLD = 80;
const MAX_TRANSLATE = 120;
 
export function attachSwipeToDismiss(element, onDismiss) {

Building a swipe-to-dismiss gesture in JS

touch-events gesture-detection dom-manipulation
Intermediate 10 steps
javascript 
const { pool } = require('./db');
 
function withTransaction() {
  return async (req, res, next) => {

A per-request transaction middleware in Express

middleware database-transactions connection-pooling
Advanced 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