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<i$ satisfying $P_j\leq P_i-K$.↵
↵
Choosing the largest valid $j$ minimizes the length $i-j$.↵
↵
## Removing Dominated Prefix Sums↵
↵
Suppose $x<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<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.↵
↵
```cpp↵
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}<P_{j_2}<\cdots<P_{j_m}$↵
↵
and↵
↵
$j_1<j_2<\cdots<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:↵
↵
```cpp↵
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<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>x$, we have $i-y<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↵
↵
```cpp↵
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>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>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.↵
↵
↵
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<i$ satisfying $P_j\leq P_i-K$.↵
↵
Choosing the largest valid $j$ minimizes the length $i-j$.↵
↵
## Removing Dominated Prefix Sums↵
↵
Suppose $x<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<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.↵
↵
```cpp↵
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}<P_{j_2}<\cdots<P_{j_m}$↵
↵
and↵
↵
$j_1<j_2<\cdots<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:↵
↵
```cpp↵
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<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>x$, we have $i-y<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↵
↵
```cpp↵
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>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>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.↵
↵
