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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Monotonic Queues and Sliding-Window Extremes.
Least You Need to Know: Monotonic Queues and Sliding-Window ExtremesRelated lessons
Keep going with nearby lessons in the same topic.