templates · Monotonic stack & deque

Monotonic deque

  • The maximum or minimum of every window of size k
  • A sliding window where you need the best element inside it, not just a sum
  • Shortest subarray with sum at least k when numbers can be negative

Monotonic deque

the one rule

The invariant

The deque holds indices inside the window, in order, with values decreasing front → back, so the front is the window's max.

write it from memory

The template

max of every window

javajava.util.*
/** Maximum of every window of size k (1 <= k <= n). The deque holds indices whose values decrease front → back. */static int[] windowMax(int[] nums, int k) {    int[] out = new int[nums.length - k + 1];    Deque<Integer> dq = new ArrayDeque<>();    for (int i = 0; i < nums.length; i++) {        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // front fell out of the window        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // they can never be the max now        dq.offerLast(i);        if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()]; // front = max of this window    }    return out;}

Two kinds of removal: from the front when an index leaves the window, from the back when a new value beats it.

fill in the blanks — only these lines change per problem

  1. line 6When the front is out of the window: index <= i - k.
  2. line 7The back-pop rule: <= for max (keep values decreasing), >= for min.
  3. line 9When a full window exists (i >= k - 1) and what to read from the front.

shortest subarray, sum >= k

javajava.util.*
/** Shortest subarray with sum >= k, negatives allowed (-1 if none). Deque of prefix indices, prefix values increasing. */static int shortestAtLeast(int[] nums, int k) {    long[] prefix = new long[nums.length + 1];    for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];    int best = Integer.MAX_VALUE;    Deque<Integer> dq = new ArrayDeque<>();    for (int i = 0; i <= nums.length; i++) {        while (!dq.isEmpty() && prefix[i] - prefix[dq.peekFirst()] >= k) // front start works: use it once            best = Math.min(best, i - dq.pollFirst());        while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[i]) dq.pollLast(); // a later, smaller start is better        dq.offerLast(i);    }    return best == Integer.MAX_VALUE ? -1 : best;}

Same deque, over prefix sums. A start index is used once and then dropped, because later ends are only longer.

fill in the blanks — only these lines change per problem

  1. line 8When the front start already reaches the goal: prefix[i] - prefix[front] >= k.

complexity

What it costs

time O(n)
Each index enters the deque once and leaves once, from the front or the back.
space O(k)
Only indices inside the current window stay in the deque (O(n) for the prefix-sum version).

watch out

Common bugs

  • Storing values instead of indices. Then you cannot tell when the front has left the window.
  • Using pollFirst where you meant pollLast (or the other way). Draw the deque once: front = oldest, back = newest.
  • Writing the answer before the first window is full, which fills out with wrong early values.

use it

Practise it on

learn it properly