Shortest Subarray With Sum at Least

$: An

$ Solution Using a Monotonic Stack and Binary Search

The standard solution uses a monotonic deque and runs in

$.

This post describes an alternative

$ approach. We maintain the useful prefix sums in a monotonic vector and binary search over it.

The idea follows from two observations:

• A smaller prefix sum is better.
• Among feasible prefix sums, a later index is better.

Prefix-sum formulation

Let

$

The sum of the subarray from

$ to

$ is

$

We require

$

or equivalently,

$

Thus, for every right endpoint

$, we need the largest index

$ satisfying

$

Choosing the largest valid

$ minimizes the length

$.

Removing dominated prefix sums

Suppose

$

and

$

Then prefix index

$ is never useful again.

For any future endpoint

$, if

$

then, because

$,

$

Moreover,

$

Therefore, whenever

$ is valid,

$ is also valid and gives a shorter subarray.

Hence, when a new prefix sum arrives, every previous prefix sum greater than or equal to it can be removed permanently.

while (!a.empty() && a.back().first >= p[i]) {
    a.pop_back();
}
a.push_back({p[i], i});

After every insertion, the stored pairs satisfy

$

and

$

Thus, the vector is increasing in both prefix sum and index.

Binary search

For the current endpoint

$, define

$

We need the last stored pair whose prefix sum is at most

$.

Since the prefix sums are increasing, all valid pairs form a prefix of the vector.

Since the indices are also increasing, the last valid pair has the largest valid index.

Therefore, we use

int pos = upper_bound(
    a.begin(),
    a.end(),
    make_pair(p[i] - k, i)
) - a.begin() - 1;

Searching for

$

finds the last stored pair satisfying

$

Correctness proof

Lemma 1

If

$ and

$, then prefix index

$ can be removed permanently after processing

$.

Proof

Whenever

$ forms a valid subarray with a future endpoint

$, we have

$

Since

$,

$

Thus,

$ is also valid. Since

$,

$

Therefore,

$ always gives a shorter subarray than

$. Hence

$ can never be optimal again.

$

Lemma 2

The maintained vector is strictly increasing in both prefix sums and indices.

Proof

Indices are inserted from left to right, so their order is increasing.

Before inserting

$, every suffix element whose prefix sum is at least

$ is removed. Therefore, the prefix sums also remain strictly increasing.

$

Theorem

For every endpoint

$, binary search returns the shortest valid subarray ending at

$.

Proof

All stored prefix sums satisfying

$

form a prefix of the vector.

Binary search returns the final element of this prefix. Since the indices are increasing, this element has the largest valid index and therefore minimizes

$.

Any removed prefix was dominated by a later prefix according to Lemma 1, so removing it cannot destroy an optimal answer.

Taking the minimum over all endpoints gives the globally shortest valid subarray.

$

Implementation

for (int i = 0; i <= n; i++) {
    while (!a.empty() && a.back().first >= p[i]) {
        a.pop_back();
    }

    a.push_back({p[i], i});

    if (i == 0) continue;

    int pos = upper_bound(
        a.begin(),
        a.end(),
        make_pair(p[i] - k, i)
    ) - a.begin() - 1;

    if (pos == -1) continue;

    ans = min(ans, i - a[pos].second);
}

Here, p is the prefix-sum array, while a stores the non-dominated pairs

$

Since the original problem has

$, inserting

$ before querying cannot create a zero-length subarray, because

$

Complexity

Each prefix sum is inserted once and removed at most once. Therefore, all stack operations together take

$.

We perform one binary search for every prefix sum, so the total running time is

$

The memory complexity is

$

Final perspective

The important object is not really a stack or deque. It is the set of non-dominated prefix states.

A state

$

is dominated by

$

whenever

$

and

$

The second state is simultaneously:

• easier to satisfy, because its prefix sum is smaller;
• better for minimizing the answer, because its index is later.

Maintaining only non-dominated states creates a monotone frontier increasing in both prefix sum and index.

The classical deque solution exploits the same dominance relation to obtain

$. This approach instead uses binary search over the monotone frontier, giving a clean

$ solution.