PK

PKBytes

Explore tracks
Chapter 30: Static Range Queries and Decomposition Techniques
30.06Intermediate / Advanced4 topics13 min4 interactive animations

Monotonic queue techniques

A monotonic deque keeps the minimum or maximum of a sliding window in amortised O(1) per element, and speeds up dynamic programming whose transitions look at a window.

Learning goals

  • Maintain the maximum or minimum of a window with a deque of indices
  • Explain why every index enters and leaves the deque once
  • Reuse the deque as a queue with an O(1) maximum
  • Speed up a windowed DP transition from O(n k) to O(n)

Prerequisites

DequeSliding windowDynamic programming basics

To find the tallest person in every group of k neighbours, you do not need to rescan each group. If someone shorter stands before a taller newcomer, the shorter one can never be the tallest again, so forget them at once.

30.06.1

Sliding window minima

Keep a deque of indices whose values are **increasing** from front to back. For each new index i, pop from the back every index whose value is greater than or equal to a[i] (they are older and no smaller, so they can never be a window minimum again), then push i. Pop the front if it has left the window. The front is then the index of the window minimum.

In the preset "Window minimum" on 1 3 -1 -3 5 3 6 7 with k = 3, the minima are [-1, -3, -3, -3, 3, 3], found with 5 removals in total. The animation shows the deque after every step.

Java
1static int[] slidingMin(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();      // indices; values increase from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] >= a[i]) dq.pollLast();   // dominated: never the minimum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];                // the front is the window minimum
9    }
10    return out;
11}

Monotonic deque: window minima, maxima and DP transitions in O(n)

Interactive · edit the input

Your input

Try

a[] (the current window is under the pointer i)

10
31
-12
-33
54
35
66
77

deque of indices (largest value at the front)

empty

window maximum

none
Setup

The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).

Step 1 / 23
Java
1int[] slidingMax(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();                     // indices; values decrease from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // dominated: never the maximum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];                // the front is the window maximum
9    }
10    return out;
11}
12int maxScore(int[] a, int k) {                   // jump at most k steps right; sum of the values visited
13    int n = a.length; int[] dp = new int[n]; dp[0] = a[0];
14    Deque<Integer> dq = new ArrayDeque<>(); dq.add(0);
15    for (int i = 1; i < n; i++) {
16        while (dq.peekFirst() < i - k) dq.pollFirst();
17        dp[i] = a[i] + dp[dq.peekFirst()];                                  // best predecessor in the window
18        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
19        dq.addLast(i);
20    }
21    return dp[n - 1];
22}

Live state

0 deque pops

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 23 steps
StepLineStateWhat happens
1L2k=3The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).
2L6i=0 value=1 size=1Add index 0.
3L5i=1 value=3 removed=03 ≥ 1: index 0 is older and no better, so it can never be the maximum of a window that contains 1. Remove it from the back.
4L6i=1 value=3 size=1Add index 1.
5L6i=2 value=-1 size=2Add index 2.
6L8i=2 window=[0, 2] answer=3Window [0, 2]: the front of the deque is index 1, so the maximum is 3.
7L6i=3 value=-3 size=3Add index 3.
8L8i=3 window=[1, 3] answer=3Window [1, 3]: the front of the deque is index 1, so the maximum is 3.
9L5i=4 value=5 removed=35 ≥ -3: index 3 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
10L5i=4 value=5 removed=25 ≥ -1: index 2 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
11L5i=4 value=5 removed=15 ≥ 3: index 1 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
12L6i=4 value=5 size=1Add index 4.
13L8i=4 window=[2, 4] answer=5Window [2, 4]: the front of the deque is index 4, so the maximum is 5.
14L6i=5 value=3 size=2Add index 5.
15L8i=5 window=[3, 5] answer=5Window [3, 5]: the front of the deque is index 4, so the maximum is 5.
16L5i=6 value=6 removed=56 ≥ 3: index 5 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
17L5i=6 value=6 removed=46 ≥ 5: index 4 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
18L6i=6 value=6 size=1Add index 6.
19L8i=6 window=[4, 6] answer=6Window [4, 6]: the front of the deque is index 6, so the maximum is 6.
20L5i=7 value=7 removed=67 ≥ 6: index 6 is older and no better, so it can never be the maximum of a window that contains 7. Remove it from the back.
21L6i=7 value=7 size=1Add index 7.
22L8i=7 window=[5, 7] answer=7Window [5, 7]: the front of the deque is index 7, so the maximum is 7.
23L10return=[3, 3, 5, 5, 6, 7] deque pops=7Window maxima: [3, 3, 5, 5, 6, 7], with 7 removals in total (at most n = 8).
30.06.2

Sliding window maxima

The maximum version is the mirror image: keep values **decreasing** from front to back, and pop from the back while a[back] <= a[i]. The preset "Window maximum" (1 3 -1 -3 5 3 6 7, k = 3) gives [3, 3, 5, 5, 6, 7] with 7 removals; "Decreasing input: the deque fills up" shows the worst case for the deque's size, since nothing is ever popped from the back and only the window edge removes elements.

Store indices, not values: the index tells you when an element leaves the window, and the value is one array read away. Using <= (not <) when popping keeps the deque free of equal values, which keeps it shorter; either choice is correct.

Java
1static int[] slidingMax(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();      // indices; values decrease from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // dominated: never the maximum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
9    }
10    return out;
11}

Monotonic deque: window minima, maxima and DP transitions in O(n)

Interactive · edit the input

Your input

Try

a[] (the current window is under the pointer i)

10
31
-12
-33
54
35
66
77

deque of indices (largest value at the front)

empty

window maximum

none
Setup

The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).

Step 1 / 23
Java
1int[] slidingMax(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();                     // indices; values decrease from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // dominated: never the maximum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];                // the front is the window maximum
9    }
10    return out;
11}
12int maxScore(int[] a, int k) {                   // jump at most k steps right; sum of the values visited
13    int n = a.length; int[] dp = new int[n]; dp[0] = a[0];
14    Deque<Integer> dq = new ArrayDeque<>(); dq.add(0);
15    for (int i = 1; i < n; i++) {
16        while (dq.peekFirst() < i - k) dq.pollFirst();
17        dp[i] = a[i] + dp[dq.peekFirst()];                                  // best predecessor in the window
18        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
19        dq.addLast(i);
20    }
21    return dp[n - 1];
22}

Live state

0 deque pops

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 23 steps
StepLineStateWhat happens
1L2k=3The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).
2L6i=0 value=1 size=1Add index 0.
3L5i=1 value=3 removed=03 ≥ 1: index 0 is older and no better, so it can never be the maximum of a window that contains 1. Remove it from the back.
4L6i=1 value=3 size=1Add index 1.
5L6i=2 value=-1 size=2Add index 2.
6L8i=2 window=[0, 2] answer=3Window [0, 2]: the front of the deque is index 1, so the maximum is 3.
7L6i=3 value=-3 size=3Add index 3.
8L8i=3 window=[1, 3] answer=3Window [1, 3]: the front of the deque is index 1, so the maximum is 3.
9L5i=4 value=5 removed=35 ≥ -3: index 3 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
10L5i=4 value=5 removed=25 ≥ -1: index 2 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
11L5i=4 value=5 removed=15 ≥ 3: index 1 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
12L6i=4 value=5 size=1Add index 4.
13L8i=4 window=[2, 4] answer=5Window [2, 4]: the front of the deque is index 4, so the maximum is 5.
14L6i=5 value=3 size=2Add index 5.
15L8i=5 window=[3, 5] answer=5Window [3, 5]: the front of the deque is index 4, so the maximum is 5.
16L5i=6 value=6 removed=56 ≥ 3: index 5 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
17L5i=6 value=6 removed=46 ≥ 5: index 4 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
18L6i=6 value=6 size=1Add index 6.
19L8i=6 window=[4, 6] answer=6Window [4, 6]: the front of the deque is index 6, so the maximum is 6.
20L5i=7 value=7 removed=67 ≥ 6: index 6 is older and no better, so it can never be the maximum of a window that contains 7. Remove it from the back.
21L6i=7 value=7 size=1Add index 7.
22L8i=7 window=[5, 7] answer=7Window [5, 7]: the front of the deque is index 7, so the maximum is 7.
23L10return=[3, 3, 5, 5, 6, 7] deque pops=7Window maxima: [3, 3, 5, 5, 6, 7], with 7 removals in total (at most n = 8).
30.06.3

O(n) deque processing

The whole pass is O(n), although there is a loop inside the loop: every index is pushed once and popped at most once, so the total number of pops over the run is at most n. This is the same amortised argument as for the monotonic stack. The deque never holds more than k indices, so the extra space is O(k).

The idea also yields a **queue with maximum**: push and pop work like a normal queue, and max() reads the front of a second deque of candidates. Each operation is amortised O(1). The animation's counter 'deque pops' totals all removals, which never exceed the number of elements.

Java
1class MaxQueue {
2    private final Deque<Integer> items = new ArrayDeque<>();
3    private final Deque<Integer> maxima = new ArrayDeque<>();   // candidates, decreasing from front to back
4    void push(int x) {
5        items.addLast(x);
6        while (!maxima.isEmpty() && maxima.peekLast() < x) maxima.pollLast();   // smaller values are dominated
7        maxima.addLast(x);
8    }
9    int pop() {                                  // removes the oldest item
10        int x = items.pollFirst();
11        if (maxima.peekFirst() == x) maxima.pollFirst();                      // it was the current maximum
12        return x;
13    }
14    int max() { return maxima.peekFirst(); }
15    boolean isEmpty() { return items.isEmpty(); }
16}

Monotonic deque: window minima, maxima and DP transitions in O(n)

Interactive · edit the input

Your input

Try

a[] (the current window is under the pointer i)

10
31
-12
-33
54
35
66
77

deque of indices (largest value at the front)

empty

window maximum

none
Setup

The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).

Step 1 / 23
Java
1int[] slidingMax(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();                     // indices; values decrease from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // dominated: never the maximum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];                // the front is the window maximum
9    }
10    return out;
11}
12int maxScore(int[] a, int k) {                   // jump at most k steps right; sum of the values visited
13    int n = a.length; int[] dp = new int[n]; dp[0] = a[0];
14    Deque<Integer> dq = new ArrayDeque<>(); dq.add(0);
15    for (int i = 1; i < n; i++) {
16        while (dq.peekFirst() < i - k) dq.pollFirst();
17        dp[i] = a[i] + dp[dq.peekFirst()];                                  // best predecessor in the window
18        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
19        dq.addLast(i);
20    }
21    return dp[n - 1];
22}

Live state

0 deque pops

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 23 steps
StepLineStateWhat happens
1L2k=3The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).
2L6i=0 value=1 size=1Add index 0.
3L5i=1 value=3 removed=03 ≥ 1: index 0 is older and no better, so it can never be the maximum of a window that contains 1. Remove it from the back.
4L6i=1 value=3 size=1Add index 1.
5L6i=2 value=-1 size=2Add index 2.
6L8i=2 window=[0, 2] answer=3Window [0, 2]: the front of the deque is index 1, so the maximum is 3.
7L6i=3 value=-3 size=3Add index 3.
8L8i=3 window=[1, 3] answer=3Window [1, 3]: the front of the deque is index 1, so the maximum is 3.
9L5i=4 value=5 removed=35 ≥ -3: index 3 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
10L5i=4 value=5 removed=25 ≥ -1: index 2 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
11L5i=4 value=5 removed=15 ≥ 3: index 1 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
12L6i=4 value=5 size=1Add index 4.
13L8i=4 window=[2, 4] answer=5Window [2, 4]: the front of the deque is index 4, so the maximum is 5.
14L6i=5 value=3 size=2Add index 5.
15L8i=5 window=[3, 5] answer=5Window [3, 5]: the front of the deque is index 4, so the maximum is 5.
16L5i=6 value=6 removed=56 ≥ 3: index 5 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
17L5i=6 value=6 removed=46 ≥ 5: index 4 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
18L6i=6 value=6 size=1Add index 6.
19L8i=6 window=[4, 6] answer=6Window [4, 6]: the front of the deque is index 6, so the maximum is 6.
20L5i=7 value=7 removed=67 ≥ 6: index 6 is older and no better, so it can never be the maximum of a window that contains 7. Remove it from the back.
21L6i=7 value=7 size=1Add index 7.
22L8i=7 window=[5, 7] answer=7Window [5, 7]: the front of the deque is index 7, so the maximum is 7.
23L10return=[3, 3, 5, 5, 6, 7] deque pops=7Window maxima: [3, 3, 5, 5, 6, 7], with 7 removals in total (at most n = 8).
30.06.4

DP transitions

Many DPs have the form dp[i] = a[i] + max(dp[j]) over a window j in [i - k, i - 1]. Computed directly this is O(n k). The window slides to the right as i grows, and the quantity needed is exactly a window maximum of the dp values, so a monotonic deque gives it in O(1) amortised and the DP runs in O(n). The only change from the plain sliding maximum is that the values are computed on the fly: add dp[i] to the deque right after computing it.

The preset "DP: jump game with scores" uses 1 -1 -2 4 -7 3 with jumps of at most k = 2: the best total score from index 0 to the last index is 7 (visiting the values 1, -1, 4 and 3). The animation shows dp and the deque side by side.

Java
1static int maxScore(int[] a, int k) {            // jump at most k steps right; sum of the values visited, ending at n - 1
2    int n = a.length;
3    int[] dp = new int[n];
4    dp[0] = a[0];
5    Deque<Integer> dq = new ArrayDeque<>();
6    dq.add(0);
7    for (int i = 1; i < n; i++) {
8        while (dq.peekFirst() < i - k) dq.pollFirst();                      // too far to jump from
9        dp[i] = a[i] + dp[dq.peekFirst()];                                  // the best predecessor in the window
10        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
11        dq.addLast(i);
12    }
13    return dp[n - 1];
14}

Monotonic deque: window minima, maxima and DP transitions in O(n)

Interactive · edit the input

Your input

Try

a[] (the current window is under the pointer i)

10
31
-12
-33
54
35
66
77

deque of indices (largest value at the front)

empty

window maximum

none
Setup

The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).

Step 1 / 23
Java
1int[] slidingMax(int[] a, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();                     // indices; values decrease from front to back
3    int[] out = new int[a.length - k + 1];
4    for (int i = 0; i < a.length; i++) {
5        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // dominated: never the maximum again
6        dq.addLast(i);
7        if (dq.peekFirst() <= i - k) dq.pollFirst();                       // left the window
8        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];                // the front is the window maximum
9    }
10    return out;
11}
12int maxScore(int[] a, int k) {                   // jump at most k steps right; sum of the values visited
13    int n = a.length; int[] dp = new int[n]; dp[0] = a[0];
14    Deque<Integer> dq = new ArrayDeque<>(); dq.add(0);
15    for (int i = 1; i < n; i++) {
16        while (dq.peekFirst() < i - k) dq.pollFirst();
17        dp[i] = a[i] + dp[dq.peekFirst()];                                  // best predecessor in the window
18        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
19        dq.addLast(i);
20    }
21    return dp[n - 1];
22}

Live state

0 deque pops

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 23 steps
StepLineStateWhat happens
1L2k=3The deque keeps indices of the window whose values are decreasing from front to back, so the front is always the maximum. A new value removes every back element that it makes useless, and the front is removed when it leaves the window. Every index enters and leaves once: O(n).
2L6i=0 value=1 size=1Add index 0.
3L5i=1 value=3 removed=03 ≥ 1: index 0 is older and no better, so it can never be the maximum of a window that contains 1. Remove it from the back.
4L6i=1 value=3 size=1Add index 1.
5L6i=2 value=-1 size=2Add index 2.
6L8i=2 window=[0, 2] answer=3Window [0, 2]: the front of the deque is index 1, so the maximum is 3.
7L6i=3 value=-3 size=3Add index 3.
8L8i=3 window=[1, 3] answer=3Window [1, 3]: the front of the deque is index 1, so the maximum is 3.
9L5i=4 value=5 removed=35 ≥ -3: index 3 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
10L5i=4 value=5 removed=25 ≥ -1: index 2 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
11L5i=4 value=5 removed=15 ≥ 3: index 1 is older and no better, so it can never be the maximum of a window that contains 4. Remove it from the back.
12L6i=4 value=5 size=1Add index 4.
13L8i=4 window=[2, 4] answer=5Window [2, 4]: the front of the deque is index 4, so the maximum is 5.
14L6i=5 value=3 size=2Add index 5.
15L8i=5 window=[3, 5] answer=5Window [3, 5]: the front of the deque is index 4, so the maximum is 5.
16L5i=6 value=6 removed=56 ≥ 3: index 5 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
17L5i=6 value=6 removed=46 ≥ 5: index 4 is older and no better, so it can never be the maximum of a window that contains 6. Remove it from the back.
18L6i=6 value=6 size=1Add index 6.
19L8i=6 window=[4, 6] answer=6Window [4, 6]: the front of the deque is index 6, so the maximum is 6.
20L5i=7 value=7 removed=67 ≥ 6: index 6 is older and no better, so it can never be the maximum of a window that contains 7. Remove it from the back.
21L6i=7 value=7 size=1Add index 7.
22L8i=7 window=[5, 7] answer=7Window [5, 7]: the front of the deque is index 7, so the maximum is 7.
23L10return=[3, 3, 5, 5, 6, 7] deque pops=7Window maxima: [3, 3, 5, 5, 6, 7], with 7 removals in total (at most n = 8).

Practice ladder

Now try it yourself

Easy

  • Sliding Window Maximum (brute force first)

Medium

  • Sliding Window Maximum
  • Jump Game VI
  • Shortest Subarray with Sum at Least K

Advanced

  • Constrained Subsequence Sum
  • Max Value of Equation
  • Longest Continuous Subarray With Absolute Diff <= Limit

Key takeaways

  • Keep indices in a deque with monotone values: pop dominated indices from the back, expired ones from the front.
  • Every index enters and leaves once, so the whole pass is O(n).
  • A DP that takes a window maximum of its own earlier values becomes O(n) with the same deque.