Monotonic queue

A monotonic queue finds the minimum (or maximum) of every window of $k$ consecutive elements of an array in $O(n)$ for the whole array. It is a deque of positions whose values increase from front to back. If you need window sums, use prefix sums; if the ranges come as arbitrary queries, use a sparse table.

Explanation

Here is an array of 8 numbers: 2, 5, 3, 7, 6, 8, 4 and 9, at positions 0 to 7. A window of 3 consecutive elements starts at the left end and slides one step to the right at a time, as in two pointers, so there are 6 windows. We want the minimum of each one. Look at the second window, positions 1 to 3: it holds 5, 3 and 7, and its minimum is 3, marked blue in Fig. 1.

Fig. 1. The second window is shaded. Its minimum is the blue 3.

The direct way, scanning every window, is correct but takes (n - k + 1) \cdot k steps. On our array that is 6 windows of 3, so 18 looks, and the windows at positions 1 to 3 and 2 to 4 both look at 3 and 7 again. For n = 10^6 and k = 5 \cdot 10^5 it is about 2.5 \cdot 10^{11} steps, while a computer does about 10^8 simple steps per second, as a rule of thumb.

A window sum can be updated in $O(1)$: add the element that enters and subtract the one that leaves. Let's do the same with the minimum and keep one number, updated with min when an element enters. On the second window it still says 2, the number at position 0 in Fig. 1, but 2 has left the window. A minimum can't be subtracted, because when the smallest element leaves, one number doesn't tell us what the next smallest is. Rescanning the window only at that moment is correct, but on an increasing array the minimum leaves at every step, and we are back to scanning every window.

So we keep several candidates. When 3 arrives, 5 is before it in the window. 5 leaves the window earlier than 3 and is larger, so every window that contains 5 contains 3 too, and 5 can never be a minimum again. In general, a new element drops every earlier candidate that is not smaller than it, the same rule as in a monotonic stack. What stays, read from the oldest, gets larger and larger, so the oldest candidate is the window's minimum. New elements join at the back, and the oldest is removed from the front when it leaves the window, so the candidates live in a deque. This deque is the monotonic queue.

For each new element there are four moves:

1. Drop: remove from the back every candidate that is not smaller than the new element.

2. Push: put the new element at the back.

3. Expire: if the front candidate has left the window, remove it from the front.

4. Read: once the first window is full, the front is the minimum.

When 7 arrives, the deque holds 2 and 3. Nothing is dropped, 7 is pushed, 2 expires, and the front is 3, the minimum of the second window.

The drop step can remove many candidates for one new element. Still, each position is pushed once and removed at most once, dropped from the back or expired from the front, so there are at most $n$ drops and expiries together. That makes at most $2n$ deque operations, $O(n)$.

The window starts at position 0 and grows to 3 cells. The new element is 2 at position 0; the deque is empty.

push: 2 goes to the back of the deque. Each deque cell shows a value with its position in small digits.

Position 1: 5 enters the window, which now holds positions 0 to 1.

push: 5 at position 1 goes to the back; the deque holds 2, 5.

Position 2: 3 enters, and the window is positions 0 to 2.

drop: 5 at position 1 is not smaller than 3, so it leaves from the back.

push: 3 at position 2 goes to the back; the deque holds 2, 3.

read: the front, 2 at position 0, is the minimum of positions 0 to 2; the blue cell marks it, and it joins the minimums in the bottom row.

Position 3: 7 enters, and the window is positions 1 to 3.

push: 7 at position 3 goes to the back; the deque holds 2, 3, 7.

expire: position 0 is before the window, so 2 leaves from the front.

read: the front, 3, is the minimum of positions 1 to 3.

Position 4: 6 enters, and the window is positions 2 to 4.

drop: 7 at position 3 is not smaller than 6, so it leaves from the back.

push: 6 at position 4 goes to the back; the deque holds 3, 6.

read: the front, 3, is the minimum of positions 2 to 4.

Position 5: 8 enters, and the window is positions 3 to 5.

push: 8 at position 5 goes to the back; the deque holds 3, 6, 8.

expire: position 2 is before the window, so 3 leaves from the front.

read: the front, 6, is the minimum of positions 3 to 5.

Position 6: 4 enters, and the window is positions 4 to 6.

drop: 8 at position 5 is not smaller than 4, so it leaves from the back.

drop: 6 at position 4 is not smaller than 4, so it leaves from the back.

push: 4 at position 6 goes to the back; the deque holds 4.

read: the front, 4, is the minimum of positions 4 to 6.

Position 7: 9 enters, and the window is positions 5 to 7.

push: 9 at position 7 goes to the back; the deque holds 4, 9.

read: the front, 4, is the minimum of positions 5 to 7. The minimums are 2 3 3 6 4 4: pushes 8, drops 4, expiries 2.

1/28

Fig. 2. Step through the run with the buttons or the arrow keys. The deque is below the array, front on the left. The blue cell is the minimum of the current window.

The minimums of the 6 windows are 2, 3, 3, 6, 4 and 4.

A problem needs this technique when it asks for the minimum or maximum of a window that only moves right, of fixed length or with both ends moved by two pointers, and $n$ is too large to scan every window. The window can't move back. After the window at positions 3 to 5, the deque holds only 6 and 8, and the 3 that the window at positions 1 to 3 needs is gone. For ranges in any order, use a sparse table.

In C++

The deque stores positions i, not values: expiry has to know whether a position has left the window. The value of a candidate is a[dq.front()], and the window that ends at i starts at i - k + 1. Each step pushes one position, so at most one expires, and if is enough.

The program reads n and k, then n integers, and prints the minimum of every window of k consecutive numbers. For the array from Fig. 1, the input is:

8 3
2 5 3 7 6 8 4 9

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // fast input: n can be 10^6
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    deque<int> dq;   // positions; their values increase from front to back
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();   // drop
        dq.push_back(i);                                             // push
        if (dq.front() <= i - k) dq.pop_front();                     // expire
        if (i >= k - 1) cout << a[dq.front()] << ' ';                // read
    }
    cout << '\n';
}

The program takes $O(n)$ time and $O(k)$ extra memory for the deque.

For window maximums, flip the drop condition: the values in the deque then decrease from front to back.

Longest window with a small spread

How long can a window be if its maximum and minimum differ by at most d? The right end r moves one step at a time, and the left end l moves forward with the two pointers rule while the window is too spread. Keep two deques: mn for the minimum and mx for the maximum. Positions expire when they fall before l.

On the array from Fig. 1 with d = 2, the window 7, 6, 8 at positions 3 to 5 has spread 2. When 4 arrives at position 6, the spread is 8 − 4 = 4. l moves right, but the 8 at position 5 stays at the front of mx until l reaches 6. So l stops at 6, and the window is the single 4 (Fig. 6).

Fig. 3. The left end moves until the spread is at most 2. A front expires only when l passes its position.

deque<int> mn, mx;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();   // drop
    mn.push_back(r);                                             // push
    while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();   // drop
    mx.push_back(r);                                             // push
    while (a[mx.front()] - a[mn.front()] > d) {   // too spread; r keeps both deques non-empty
        l++;
        if (mn.front() < l) mn.pop_front();                      // expire
        if (mx.front() < l) mx.pop_front();                      // expire
    }
    best = max(best, r - l + 1);
}

On this array the answer is 3, positions 3 to 5. Both ends only move right, so this is still $O(n)$.

A queue that reports its minimum

A queue where items are added at the back and removed from the front can also report its minimum. Items leave in the order they arrived, so the items in the queue are the window, and mn is the monotonic queue over them. Keep the items in a vector a in arrival order; the queue is the part from position head to the end. The vector keeps every item ever added, so it takes memory for all the additions, not only for the current queue.

vector<int> a;    // every item added so far
int head = 0;     // the queue is a[head], ..., a.back()
deque<int> mn;    // positions; their values increase from front to back

// add x
a.push_back(x);
while (!mn.empty() && a[mn.back()] >= x) mn.pop_back();   // drop
mn.push_back(a.size() - 1);                               // push

// remove the front item, when the queue is not empty
head++;
if (mn.front() < head) mn.pop_front();                    // expire

// the minimum, when the queue is not empty: a[mn.front()]

Take add 3, add 1, add 4, remove, remove. The 1 drops 3, so mn holds 1, then 1 and 4. The first removal takes 3 out of the queue and leaves mn alone, since 3 was already dropped. The second removal takes out 1, which expires, and the minimum becomes 4.

Every item is pushed once and removed at most once, so $m$ operations take $O(m)$ in total, even though one addition can drop many items.

Common mistakes

• Storing values instead of positions. Expiry can then only compare values, dq.front() == a[i - k], and an equal value that was dropped takes its twin out too early: on 3, 3, 5 with k = 2 the program prints 3 5 instead of 3 3. Store positions and expire with dq.front() <= i - k.

• Expiring with dq.front() < i - k. A position stays in the deque one step after it has left the window, and the array from Fig. 1 gives 2 2 3 3 4 4 instead of 2 3 3 6 4 4.

• Dropping with if instead of while. Only one candidate goes, and the values stop increasing. In the array from Fig. 1, 4 drops 8 but not 6, and the output is 2 3 3 6 6 4.

Similar techniques

A monotonic stack finds the nearest smaller or greater element of each position, not the minimum of a moving window.

If the array changes between range queries, use a segment tree instead of a sparse table.

In dynamic programming where each state depends on the best of the last $k$ states, a monotonic queue over the earlier states gives that best value. There the front is read before the new state is pushed, so the window ends one step earlier than in the template.

Practice