practice · hard · from Queues

Sliding Window Maximum

time: O(n)
space: O(k)
tags: queues · monotonic-deque · sliding-window

in the wild Streaming sensor signal: report the maximum reading in the last k samples — a Kalman filter's gate threshold, a vibration-spike detector, a sliding-confidence summary.

Sliding window · monotonic deque

…

speed step 0 / 0

Problem

Given an integer array nums of length n and a window size k, return an array of length n - k + 1 where each element is the maximum of the k-element window ending at that position.

Examples

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]
- Window [1, 3, -1] → 3
- Window [3, -1, -3] → 3
- Window [-1, -3, 5] → 5
- Window [-3, 5, 3] → 5
- Window [5, 3, 6] → 6
- Window [3, 6, 7] → 7
nums = [4, 4, 4, 4], k = 2 → [4, 4, 4]
nums = [1], k = 1 → [1]

Why this is the canonical monotonic-deque problem

Naïve: for each window, scan its k elements to find the max. O(n·k) total — fine for small k, hopeless for streams.

A min/max-heap gets you O(n log k). Acceptable but not optimal.

The optimal O(n) solution uses a monotonic deque — a double-ended queue that always holds the indices of "still-potentially-maximum" candidates in decreasing-value order. As we slide:

From the back: pop every index whose value is ≤ the new value — those candidates can never be the max again as long as the new one is in the window.
From the front: pop the head if it's fallen out of the window (index < i - k + 1).
Push the new index at the back.
The current window's max is at the deque's front.

Each index is pushed and popped at most once, so total work is O(n). This generalizes the monotonic-stack pattern into a sliding-window context.

Hints

Hint 1 — what to keep around

For each new window, you need the maximum quickly. What if you maintained a structure where the maximum was always at one end? When would a candidate become permanently obsolete?

Hint 2 — the deque invariant

A candidate at index j is permanently irrelevant if a later index i > j has nums[i] ≥ nums[j] — because for every window containing j, that window also contains i, and i's value is at least as good. So you can drop j.

This means the deque (read front-to-back) is always strictly decreasing in value.

Hint 3 — pseudocode

result = []
deque  = []                    # holds indices, values strictly decreasing
for i in range(n):
    # 1. Drop tail while its value ≤ nums[i].
    while deque and nums[deque[-1]] <= nums[i]:
        deque.pop()
    # 2. Push the new index.
    deque.append(i)
    # 3. Drop head if it's outside the window.
    if deque[0] <= i - k:
        deque.popleft()
    # 4. Once we have a full window, emit the max (front of deque).
    if i >= k - 1:
        result.append(nums[deque[0]])

Solution

from collections import deque

def sliding_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()    # holds indices; values strictly decreasing
    out: list[int] = []
    for i, v in enumerate(nums):
        while dq and nums[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

cases = [
    ([1, 3, -1, -3, 5, 3, 6, 7], 3, [3, 3, 5, 5, 6, 7]),
    ([4, 4, 4, 4],                2, [4, 4, 4]),
    ([1],                         1, [1]),
    ([9, 8, 7, 6, 5],             3, [9, 8, 7]),
    ([1, 2, 3, 4, 5],             3, [3, 4, 5]),
]
for nums, k, expected in cases:
    got  = sliding_max(nums, k)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} sliding_max({nums}, k={k}) = {got}")

function slidingMax(nums, k) {
  const dq  = [];                // indices; values strictly decreasing
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (dq[0] <= i - k) dq.shift();
    if (i >= k - 1) out.push(nums[dq[0]]);
  }
  return out;
}

const cases = [
  [[1, 3, -1, -3, 5, 3, 6, 7], 3, [3, 3, 5, 5, 6, 7]],
  [[4, 4, 4, 4],                2, [4, 4, 4]],
  [[1],                         1, [1]],
  [[9, 8, 7, 6, 5],             3, [9, 8, 7]],
  [[1, 2, 3, 4, 5],             3, [3, 4, 5]],
];
for (const [nums, k, expected] of cases) {
  const got = slidingMax(nums, k);
  const ok  = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} slidingMax(${JSON.stringify(nums)}, k=${k}) = ${JSON.stringify(got)}`);
}

use std::collections::VecDeque;

pub fn sliding_max(nums: &[i32], k: usize) -> Vec<i32> {
    let mut dq: VecDeque<usize> = VecDeque::new();   // indices
    let mut out = Vec::new();
    for (i, &v) in nums.iter().enumerate() {
        while let Some(&back) = dq.back() {
            if nums[back] <= v { dq.pop_back(); } else { break; }
        }
        dq.push_back(i);
        if let Some(&front) = dq.front() {
            if front + k <= i { dq.pop_front(); }
        }
        if i + 1 >= k {
            out.push(nums[*dq.front().unwrap()]);
        }
    }
    out
}

fn main() {
    let cases: &[(&[i32], usize, &[i32])] = &[
        (&[1, 3, -1, -3, 5, 3, 6, 7], 3, &[3, 3, 5, 5, 6, 7]),
        (&[4, 4, 4, 4],                2, &[4, 4, 4]),
        (&[1],                         1, &[1]),
        (&[9, 8, 7, 6, 5],             3, &[9, 8, 7]),
        (&[1, 2, 3, 4, 5],             3, &[3, 4, 5]),
    ];
    for (nums, k, expected) in cases {
        let got  = sliding_max(nums, *k);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} sliding_max({:?}, k={}) = {:?}", nums, k, got);
    }
}

#include <deque>
#include <iostream>
#include <vector>

std::vector<int> sliding_max(const std::vector<int>& nums, int k) {
    std::deque<int> dq;     // indices; values strictly decreasing
    std::vector<int> out;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) out.push_back(nums[dq.front()]);
    }
    return out;
}

int main() {
    struct Case { std::vector<int> nums; int k; std::vector<int> expected; };
    std::vector<Case> cases = {
        {{1, 3, -1, -3, 5, 3, 6, 7}, 3, {3, 3, 5, 5, 6, 7}},
        {{4, 4, 4, 4},                2, {4, 4, 4}},
        {{1},                         1, {1}},
        {{9, 8, 7, 6, 5},             3, {9, 8, 7}},
        {{1, 2, 3, 4, 5},             3, {3, 4, 5}},
    };
    for (auto& c : cases) {
        auto got = sliding_max(c.nums, c.k);
        std::cout << (got == c.expected ? "✓" : "✗") << " sliding_max(.., k=" << c.k << ") = {";
        for (size_t i = 0; i < got.size(); ++i)
            std::cout << got[i] << (i + 1 < got.size() ? "," : "");
        std::cout << "}\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

// Returns a malloc'd array of length n - k + 1; caller frees.
int* sliding_max(const int* nums, int n, int k, int* out_len) {
    *out_len = n - k + 1;
    int* out = malloc(*out_len * sizeof(int));
    int* dq  = malloc(n * sizeof(int));     // ring of indices (we use as deque)
    int  head = 0, tail = 0;                 // [head, tail) is the deque
    for (int i = 0; i < n; i++) {
        while (head < tail && nums[dq[tail - 1]] <= nums[i]) tail--;
        dq[tail++] = i;
        if (dq[head] <= i - k) head++;
        if (i >= k - 1) out[i - k + 1] = nums[dq[head]];
    }
    free(dq);
    return out;
}

static void show(const int* nums, int n, int k, const int* expected) {
    int  out_len;
    int* got = sliding_max(nums, n, k, &out_len);
    int  ok  = 1;
    for (int i = 0; i < out_len; i++) if (got[i] != expected[i]) { ok = 0; break; }
    printf("%s sliding_max(.., k=%d) = {", ok ? "✓" : "✗", k);
    for (int i = 0; i < out_len; i++) printf("%d%s", got[i], i + 1 < out_len ? "," : "");
    printf("}\n");
    free(got);
}

int main(void) {
    int a [] = {1, 3, -1, -3, 5, 3, 6, 7};  int ea[] = {3, 3, 5, 5, 6, 7};  show(a, 8, 3, ea);
    int b [] = {4, 4, 4, 4};                int eb[] = {4, 4, 4};            show(b, 4, 2, eb);
    int c [] = {1};                         int ec[] = {1};                  show(c, 1, 1, ec);
    int d [] = {9, 8, 7, 6, 5};             int ed[] = {9, 8, 7};            show(d, 5, 3, ed);
    int e [] = {1, 2, 3, 4, 5};             int ee[] = {3, 4, 5};            show(e, 5, 3, ee);
    return 0;
}

idle

The monotonic deque is one of the most powerful "fancy queue" tricks in the algorithms canon. Stack-only solutions are O(n log k) with a heap, but the deque lets us drop dominated candidates eagerly — keeping the data structure exactly as large as it needs to be, never larger.

Complexity

Time: O(n) amortized. Even though one outer step can pop many elements, each index enters and leaves the deque at most once across the whole run.
Space: O(k) — the deque holds at most k indices at a time (older ones are evicted by the window-slide step).
vs heap-based: A max-heap of (value, index) pairs gives O(n log k). For very large k this gap matters. For small k the heap is often faster constant-factor — measure if it matters.

In the wild

Streaming peak-detection in real-time sensor pipelines — "max vibration in the last 100 ms".
Trading systems — "highest bid in the last k ticks" feeds into spike-detection logic.
Robot health monitoring — sliding-window confidence / error / latency stats.
Stream-processing engines — Apache Flink and Kafka Streams have built-in sliding-window aggregates that use this algorithm internally.

Variations

Sliding minimum. Flip the comparison — the deque holds increasing values, and the front is the min.
Sliding-window median — much harder; requires either two heaps or a sorted-skiplist. O(n log k).
Sliding sum. Trivial — keep a running sum, add new, subtract old. O(n).
All-window K-th largest. Multiset / order-statistics tree → O(n log k).