Sliding window maximum (deque)

Report the largest value in every window of size k, using a double-ended queue that keeps only useful candidates.

Time O(n)Space O(k)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A value can never be the maximum again once a larger value arrives after it, so throw it away. What remains is a decreasing line of candidates with the current maximum at the front.

Code

C++PythonC#

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

from collections import deque

def max_sliding_window(a: list[int], k: int) -> list[int]:
    dq = deque()  # indices, values decreasing
    result = []
    for i, x in enumerate(a):
        if dq and dq[0] <= i - k: dq.popleft()
        while dq and a[dq[-1]] <= x: dq.pop()
        dq.append(i)
        if i >= k - 1: result.append(a[dq[0]])
    return result

public static int[] MaxSlidingWindow(int[] a, int k) {
    var dq = new LinkedList<int>(); // indices, values decreasing
    var result = new List<int>();
    for (int i = 0; i < a.Length; i++) {
        if (dq.Count > 0 && dq.First.Value <= i - k) dq.RemoveFirst();
        while (dq.Count > 0 && a[dq.Last.Value] <= a[i]) dq.RemoveLast();
        dq.AddLast(i);
        if (i >= k - 1) result.Add(a[dq.First.Value]);
    }
    return result.ToArray();
}

Tips

Remove from the back when a bigger value arrives, and from the front when an index slides out of the window.
A monotonic stack that can also drop items from the bottom is a monotonic deque.

In the .NET library

.NET has no Deque<T>. LinkedList<T> gives O(1) AddLast, RemoveFirst and RemoveLast, which is everything a deque needs.