The standard solution uses a monotonic deque and runs in $$$O(n)$$$.

This post describes an alternative $$$O(n\log n)$$$ approach. We maintain the useful prefix sums in a monotonic vector and binary search over it.

The idea comes from two observations:

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

Prefix Sum Formulation

Let $$$P_0=0$$$ and $$$P_i=a_1+a_2+\cdots+a_i$$$.

The sum of the subarray from $$$j+1$$$ to $$$i$$$ is $$$P_i-P_j$$$.

We require $$$P_i-P_j\geq K$$$, or equivalently,

$$$P_j\leq P_i-K$$$.

Therefore, for every right endpoint $$$i$$$, we need the largest index $$$j \lt i$$$ satisfying $$$P_j\leq P_i-K$$$.

Choosing the largest valid $$$j$$$ minimizes the length $$$i-j$$$.

Removing Dominated Prefix Sums

Suppose $$$x \lt y$$$ and $$$P_y\leq P_x$$$.

Then prefix index $$$x$$$ is never useful again.

Indeed, if $$$P_i-P_x\geq K$$$, then

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

because $$$P_y\leq P_x$$$.

Moreover, $$$i-y \lt i-x$$$, so using $$$y$$$ always gives a shorter subarray.

Hence, whenever 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

$$$P_{j_1} \lt P_{j_2} \lt \cdots \lt P_{j_m}$$$

and

$$$j_1 \lt j_2 \lt \cdots \lt j_m$$$.

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

Binary Search

For the current endpoint $$$i$$$, define $$$T=P_i-K$$$.

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

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 $$$(P_i-K,i)$$$ finds the last stored pair satisfying $$$P_j\leq P_i-K$$$.

Correctness

Lemma 1

If $$$x \lt y$$$ and $$$P_y\leq P_x$$$, then prefix index $$$x$$$ can be removed permanently.

Proof.

Whenever $$$x$$$ forms a valid subarray with a future endpoint $$$i$$$, the index $$$y$$$ also forms a valid subarray because $$$P_y\leq P_x$$$.

Since $$$y \gt x$$$, we have $$$i-y \lt i-x$$$. Therefore, $$$y$$$ always gives a shorter subarray, so $$$x$$$ 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. Before inserting a new prefix sum, every suffix whose value is greater than or equal to it is removed. Hence both coordinates remain strictly increasing.

Theorem

For every endpoint $$$i$$$, binary search returns the shortest valid subarray ending at $$$i$$$.

Proof.

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

Every removed prefix is dominated by a later prefix by Lemma 1, so removing it cannot destroy an optimal answer.

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

Implementation

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

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

    if (i > 0) {
        int p1 = upper_bound(
            a.begin(),
            a.end(),
            make_pair(p[i] - k, i)
        ) - a.begin() - 1;

        if (p1 == -1) continue;

        int l = a[p1].second;
        ans = min(ans, i - l);
    }
}

Here, p is the prefix sum array, while a stores the non-dominated pairs $$$(P_j,j)$$$.

Since the original problem has $$$K \gt 0$$$, inserting $$$(P_i,i)$$$ before querying cannot create a zero-length answer because $$$P_i\not\leq P_i-K$$$.

Complexity

Each prefix sum is inserted once and removed at most once, so all stack operations together take $$$O(n)$$$.

We perform one binary search for every prefix sum, giving a total time complexity of $$$O(n\log n)$$$.

The memory complexity is $$$O(n)$$$.

Final Perspective

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

A state $$$(P_x,x)$$$ is dominated by $$$(P_y,y)$$$ whenever $$$P_y\leq P_x$$$ and $$$y \gt x$$$.

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 $$$O(n)$$$. This approach instead binary searches over the monotone frontier, giving a clean $$$O(n\log n)$$$ solution.