Prefix Sum Candidates

When To Use

Use this when candidates are prefix indices and the deque keeps the best prefix sums.

This is not the normal max/min window. The deque stores possible left endpoints.

Template

for i = 0; i <= n; i++:
    while dq not empty and prefix[i] - prefix[dq.front] satisfies target:
        update answer
        pop front
 
    while dq not empty and prefix[dq.back] >= prefix[i]:
        pop back
 
    push i

The back-pop says: a newer lower prefix is always better than an older higher prefix.

Problems

Shortest Subarray With Sum At Least K

Problem: shortest subarray whose sum is at least k, with negative values allowed.

Pattern: increasing deque of prefix sums.

Applied pseudocode:

build prefix[0..n]
 
for i = 0; i <= n; i++:
    while dq not empty and prefix[i] - prefix[dq.front] >= k:
        ans = min(ans, i - dq.front)
        dq.pop_front()
 
    while dq not empty and prefix[dq.back] >= prefix[i]:
        dq.pop_back()
 
    dq.push_back(i)