Sliding window maximum with monotonic deque in Python

Keep a deque of candidate indices in decreasing value order; solves the problem in O(n) total time.

File: sliding_window_maximum_deque.py, 43 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

sliding_window_maximum_deque.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sliding-window-maximum-deque/. The authors are listed in prov/N2ZTTV.jsonl.

from collections import deque
from typing import Any


def sliding_window_maximum(a: list[Any], k: int) -> list[Any]:
    """Return [max(a[l:l + k]) for l in range(len(a) - k + 1)].

    Precondition: k >= 1. Returns [] when k > len(a).
    Cost: O(n) time in total, O(k) extra space.
    """
    if k < 1:
        raise ValueError("k must be at least 1")
    d: deque[int] = deque()  # @line L1
    m: list[Any] = []
    for r in range(len(a)):  # @line L2
        while d and a[d[-1]] <= a[r]:  # @line L3
            d.pop()
        d.append(r)  # @line L4
        if d[0] <= r - k:  # @line L5
            d.popleft()
        if r >= k - 1:  # @line L6
            m.append(a[d[0]])
    return m  # @line L7


def sliding_window_minimum(a: list[Any], k: int) -> list[Any]:
    """Return [min(a[l:l + k]) for l in range(len(a) - k + 1)], by the mirror test."""
    if k < 1:
        raise ValueError("k must be at least 1")
    d: deque[int] = deque()
    m: list[Any] = []
    for r in range(len(a)):
        while d and a[d[-1]] >= a[r]:
            d.pop()
        d.append(r)
        if d[0] <= r - k:
            d.popleft()
        if r >= k - 1:
            m.append(a[d[0]])
    return m

test_sliding_window_maximum_deque.py 38 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sliding-window-maximum-deque/. The authors are listed in prov/N2ZTTV.jsonl.

import random

import pytest

from sliding_window_maximum_deque import sliding_window_maximum, sliding_window_minimum


def test_example() -> None:
    assert sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
    assert sliding_window_minimum([1, 3, -1, -3, 5, 3, 6, 7], 3) == [-1, -3, -3, -3, 3, 3]


def test_edges() -> None:
    assert sliding_window_maximum([], 1) == []
    assert sliding_window_maximum([4], 1) == [4]
    assert sliding_window_maximum([1, 2], 3) == []
    assert sliding_window_maximum([5, 1, 1], 2) == [5, 1]
    assert sliding_window_maximum([2, 2, 2, 2], 2) == [2, 2, 2]
    assert sliding_window_maximum([4, 3, 2, 1], 4) == [4]
    assert sliding_window_maximum([1, 2, 3, 4], 1) == [1, 2, 3, 4]
    assert sliding_window_maximum([9, 8, 7, 6, 5], 2) == [9, 8, 7, 6]
    with pytest.raises(ValueError):
        sliding_window_maximum([1], 0)


def test_against_brute_force() -> None:
    rng = random.Random(20261104)
    for _ in range(2000):
        n = rng.randrange(0, 20)
        k = rng.randrange(1, n + 2)
        a = [rng.randrange(-5, 6) for _ in range(n)]
        want_max = [max(a[i : i + k]) for i in range(n - k + 1)]
        want_min = [min(a[i : i + k]) for i in range(n - k + 1)]
        assert sliding_window_maximum(a, k) == want_max
        assert sliding_window_minimum(a, k) == want_min

What the next level needs

the tests did not run in this build

Read the full page about Sliding window maximum with monotonic deque