Monotonic queue

When to use it

Use it when a window, a stretch of neighbors, moves along a list and you need its largest or smallest value at every position, which a running total cannot give.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A long rope has a strength measured at each meter. A piece of rope is only as strong as its weakest meter. Return the strength of the strongest piece that is exactly 3 meters long.

Input
strengths = [3, 6, 5, 7, 8]
k = 3

Output
5

The method

1. Keep a queue of positions; their values rise from front to back
2. Drop the front position once it has left the window
3. Drop from the back all values not smaller than the new one
4. Add the new position at the back
5. The front is the weakest of a full window: keep the best
6. Return the strength of the strongest piece

The run, one moment at a time

1. Step 1. The queue is empty. It will hold positions. The picture shows the value at each position, with the front of the queue on the left.

   strengths: 3 6 5 7 8
   queue: empty
   best: 0
   

2. Step 4. Meter 0 has strength 3. The queue is empty, so position 0 joins it.

   strengths: 3 6 5 7 8  (both at 0)
   queue: 3  (at 0 at 0)
   best: 0
   

3. Step 4. Meter 1 has strength 6. The 3 at the back is smaller, so it stays. Position 1 joins at the back.

   strengths: 3 6 5 7 8  (left at 0, right at 1)
   queue: 3 6  (at 0 at 0, at 1 at 1)
   best: 0
   

4. Step 3. Meter 2 has strength 5. The 6 at the back is not smaller, so it is dropped: 5 is weaker and stays in the window longer. The 3 before it is smaller, so it stays.

   strengths: 3 6 5 7 8  (left at 0, right at 2)
   queue: 3  (at 0 at 0)
   best: 0
   

5. Step 4. Position 2 joins at the back. The values in the queue, 3 and 5, rise from front to back.

   strengths: 3 6 5 7 8  (left at 0, right at 2)
   queue: 3 5  (at 0 at 0, at 2 at 1)
   best: 0
   

6. Step 5. Meters 0 to 2 are the first full window. Its weakest meter is at the front of the queue: 3. That is more than the best, 0, so the best becomes 3.

   strengths: 3 6 5 7 8  (left at 0, right at 2)
   queue: 3 5  (at 0 at 0, at 2 at 1)
   best: 3
   

7. Step 2. The window is now meters 1 to 3. The front of the queue is position 0, which is outside it, so it is dropped. The 5 becomes the front.

   strengths: 3 6 5 7 8  (left at 1, right at 3)
   queue: 5  (at 2 at 0)
   best: 3
   

8. Step 4. Meter 3 has strength 7. The 5 at the back is smaller, so it stays. Position 3 joins at the back.

   strengths: 3 6 5 7 8  (left at 1, right at 3)
   queue: 5 7  (at 2 at 0, at 3 at 1)
   best: 3
   

9. Step 5. The front of the queue is 5: the weakest of meters 1 to 3. That is more than the best, 3, so the best becomes 5.

   strengths: 3 6 5 7 8  (left at 1, right at 3)
   queue: 5 7  (at 2 at 0, at 3 at 1)
   best: 5
   

10. Step 4. Meter 4 has strength 8. The 7 at the back is smaller, so it stays. Position 4 joins at the back.

    strengths: 3 6 5 7 8  (left at 2, right at 4)
    queue: 5 7 8  (at 2 at 0, at 3 at 1, at 4 at 2)
    best: 5
    

11. Step 5. The front of the queue is 5: the weakest of meters 2 to 4. That is not more than the best, 5, so the best stays.

    strengths: 3 6 5 7 8  (left at 2, right at 4)
    queue: 5 7 8  (at 2 at 0, at 3 at 1, at 4 at 2)
    best: 5
    

12. Step 6. Each position joined the queue once and left it at most once. The strongest piece of 3 meters has strength 5: its weakest meter is at position 2.

    strengths: 3 6 5 7 8
    queue: 5 7 8  (at 2 at 0, at 3 at 1, at 4 at 2)
    best: 5
    

The code

The numbered comments are the steps of the method.

function solve(strengths, k) {
  // 1. Keep a queue of positions; their values rise from front to back
  const queue = [];
  // Removing a list's first entry moves all the others,
  // so head marks the front of the queue instead.
  let head = 0;
  let best = 0;
  for (let right = 0; right < strengths.length; right++) {
    // 2. Drop the front position once it has left the window
    while (head < queue.length && queue[head] <= right - k) head += 1;
    // 3. Drop from the back all values not smaller than the new one
    while (
      head < queue.length &&
      strengths[queue[queue.length - 1]] >= strengths[right]
    ) {
      queue.pop();
    }
    // 4. Add the new position at the back
    queue.push(right);
    // 5. The front is the weakest of a full window: keep the best
    if (right >= k - 1 && strengths[queue[head]] > best) {
      best = strengths[queue[head]];
    }
  }
  // 6. Return the strength of the strongest piece
  return best;
}

from collections import deque


def solve(strengths, k):
    # 1. Keep a queue of positions; their values rise from front to back
    queue = deque()
    best = 0
    for right in range(len(strengths)):
        # 2. Drop the front position once it has left the window
        while queue and queue[0] <= right - k:
            queue.popleft()
        # 3. Drop from the back all values not smaller than the new one
        while queue and strengths[queue[-1]] >= strengths[right]:
            queue.pop()
        # 4. Add the new position at the back
        queue.append(right)
        # 5. The front is the weakest of a full window: keep the best
        if right >= k - 1 and strengths[queue[0]] > best:
            best = strengths[queue[0]]
    # 6. Return the strength of the strongest piece
    return best

How to spot it

Asked: The smallest value of every k items in a row

A total can be corrected when an item leaves the window. A smallest value cannot, so you keep the values that could be smallest next.

Asked: After each new reading, the highest of the last k readings

A new reading that is higher makes every older, lower reading useless: the new one stays in the window longer. Drop them, and the highest is at the front.

Limits: Aim for O(n) time; searching each window again is too slow

Searching every window costs about n times k steps. In the queue each value joins once and leaves once, about 2n steps.

Looks like it, but is not

• You need the total or a count of every k items in a row. Use Fixed-size sliding window. A total is corrected with one addition and one subtraction as the window moves. No candidates have to be kept.
• For each value, you need the next larger value to its right. Use Monotonic stack. There no value becomes too old, so values leave at one end only. A queue is needed when the oldest must also leave.
• You want the longest stretch whose total stays within a limit. Use Variable sliding window. The rule is about a total, which one number can follow. The largest or smallest value of the window is never asked for.

Cost and mistakes

Time grows with the number of values, written O(n): each position joins the queue once and leaves it at most once. Extra space is the queue: at most k positions wait in it at a time, written O(k).

Watch out

• Keep positions in the queue, not values. Only a position can tell you that the front has left the window.
• Read the front only after the old front is dropped and the new value is added. The new value may be the smallest of its window.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.