Algorithms / Monotonic Deque Prefix Sum
Least You Need to Know: Monotonic Deques, Prefix Sums, and Shortest Valid Windows
Some subarray problems use prefix sums plus a monotonic deque over prefix indices. The deque keeps promising earlier prefixes in increasing order so the current prefix can quickly detect the shortest earlier start that already makes the sum large enough.
The least you need to know
- Subarray sums become differences of prefix sums.
- For shortest-subarray-at-least-K problems, an increasing deque of prefix sums keeps only promising starts.
- If a later prefix sum is smaller than an earlier one, the earlier larger prefix is dominated for future shortest-window searches.
- When the current prefix minus the deque front already meets the target, popping from the front can improve the length.
- This pattern is more specialized than ordinary fixed-size sliding windows.
Key notation
P[i]
prefix sum of the first i elements
P[j] - P[i]
sum of the subarray from i to j-1
dominated prefix
an earlier prefix with a larger sum than a later candidate
Tiny worked example
- Build prefix sums `P[0], P[1], ..., P[n]`.
- Maintain deque indices whose prefix sums are increasing.
- At each new prefix `P[j]`, pop from the front while `P[j] - P[front]` already meets the target, recording shorter lengths.
- Pop from the back while `P[j]` is smaller than the back prefix, because the back is dominated.
Common mistakes
- Students often reach for a standard sliding window even when negative numbers break that approach.
- Students often forget that prefix indices, not array values, belong in the deque.
- Students often miss the domination rule that removes worse earlier prefixes from the back.
How to recognize this kind of problem
- The prompt asks for a shortest or earliest-valid subarray meeting a sum threshold.
- Negative numbers prevent a simple expand-shrink window.
- Prefix sums turn the condition into comparisons between earlier and later prefix values.