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

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

Related explainers

javascript

const ROLE_PERMISSIONS = {
  admin: ['users:read', 'users:write', 'billing:read', 'billing:write'],
  manager: ['users:read', 'billing:read'],
  member: ['users:read'],

Role-based permissions middleware in Express

authorization middleware rbac

Intermediate 9 steps

javascript

function attachThousandSeparators(input, { locale = 'en-US' } = {}) {
  const formatter = new Intl.NumberFormat(locale);
  const groupSep = formatter.format(11111).replace(/\d/g, '')[0] || ',';
  const decimalSep = formatter.format(1.1).replace(/\d/g, '')[0] || '.';

Live thousand separators without losing the caret

dom intl caret-preservation

Advanced 8 steps

javascript

import { useReducer, useEffect } from "react";
 
const initialState = { status: "idle", data: null, error: null };

Building a data-fetching hook in React

custom-hooks usereducer data-fetching

Intermediate 9 steps

javascript

const express = require('express');
const app = express();
 
app.get('/health', (req, res) => res.json({ status: 'ok' }));

Graceful shutdown in an Express server

graceful-shutdown signal-handling connection-tracking

Advanced 9 steps

javascript

import { useState, useEffect, useCallback } from 'react';
 
function getColumnCount(width) {
  if (width < 640) return 1;

A responsive column hook in React

custom-hooks debouncing responsive-design

Intermediate 7 steps

javascript

function initCharacterCounter(textarea, options = {}) {
  const maxLength = options.maxLength ?? 280;
  const warnThreshold = options.warnThreshold ?? 0.9;