The standard solution to this problem uses a monotonic deque and runs in

$.

This post describes a different approach running in

$. Instead of maintaining a deque, we store the useful prefix sums in a monotonic vector and binary-search over it.

The whole idea comes from two simple observations:

1. A smaller prefix sum is always better.
2. If two prefix sums are equally good, the later index is always better.

Prefix Sum Formulation

Let

$ P_0=0,\qquad P_i=a_1+a_2+\cdots+a_i.

$

Then the sum of the subarray

$ equals

$ P_i-P_j.

$

We want

$ P_i-P_j\ge K,

$

or equivalently,

$ P_j\le P_i-K.

$

Therefore, for every right endpoint

$, we need the largest index

$ satisfying

$ P_j\le P_i-K.

$

Choosing the largest valid

$ minimizes the subarray length

$.

Removing Dominated Prefix Sums

Suppose

$ x<y

$

and

$ P_y\le P_x.

$

Then the prefix

$ is never useful again.

Indeed, if some future endpoint

$ satisfies

$ P_i-P_x\ge K,

$

then

$ P_i-P_y \ge P_i-P_x \ge K,

$

because

$.

Moreover,

$ i-y<i-x,

$

so using

$ always produces a shorter subarray.

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

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

After every insertion, the stored pairs satisfy

$ P_{j_1}<P_{j_2}<\cdots<P_{j_m},

$

and their indices also satisfy

$ j_1<j_2<\cdots<j_m.

$

Thus the vector is strictly increasing in both coordinates.

Binary Search

For the current endpoint

$, define

$ T=P_i-K.

$

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

$.

Since prefix sums are strictly increasing, every valid pair forms a prefix of the vector.

Since indices are also strictly increasing, the last valid pair has the largest possible index, exactly the one we want.

Therefore we simply do

[code=cpp] int pos = upper_bound( a.begin(), a.end(), make_pair(p[i] — k, i) ) — a.begin() — 1; [/code]

Searching for the pair

$ ensures that every stored prefix sum satisfying

$ is included.

Why Does This Work?

Lemma 1

If

$ and

$, then

$ can be removed forever.

Proof.

Whenever

$ forms a valid subarray with some future endpoint,

$ also forms a valid one because its prefix sum is no larger. Since

$, it always produces a shorter subarray. Hence

$ is never optimal again. ▢

Lemma 2

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

Proof.

Indices are inserted from left to right. Before inserting a new prefix sum, all larger (or equal) suffix prefix sums are removed. Therefore both coordinates remain strictly increasing. ▢

Theorem

For every endpoint

$, the binary search returns the shortest valid subarray ending at

$.

Proof.

All feasible prefix sums form a prefix of the vector. Binary search returns the last element of this prefix, which has the largest valid index.

By Lemma 1, every removed prefix is dominated by another one, so deleting it never removes an optimal answer.

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

Implementation

[code=cpp] 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);

} [/code]

Here:

• p is the prefix sum array.
• a stores the non-dominated pairs

$.

For the original problem,

$, so inserting

$ before querying cannot create a zero-length answer because

$ P_i\not\le P_i-K.

$

Complexity

Each prefix sum is

• inserted once,
• removed at most once.

Thus all stack operations together take

$.

We perform one binary search for every prefix, so the total complexity is

$ O(n\log n).

$

Memory complexity is

$ O(n).

$

Final Perspective

The key object is not really a stack or a deque—it is the set of non-dominated prefix states.

A state

$ is dominated by

$ whenever

$ P_y\le P_x \quad\text{and}\quad y>x.

$

The second state is simultaneously

• easier to satisfy (smaller prefix sum),
• better for minimizing the answer (later index).

Maintaining only these non-dominated states creates a monotone frontier that is increasing in both prefix sum and index. The monotonic deque solution exploits the same dominance relation to achieve

$, while this approach replaces deque queries with binary search, yielding a simpler

$ alternative.