Solution
Approach 1: Sliding Window
Intuition
We can rephrase this as a problem about the prefix sums of A
. Let P[i] = A[0] + A[1] + ... + A[i1]
. We want the smallest yx
such that y > x
and P[y]  P[x] >= K
.
Motivated by that equation, let opt(y)
be the largest x
such that P[x] <= P[y]  K
. We need two key observations:

If
x1 < x2
andP[x2] <= P[x1]
, thenopt(y)
can never bex1
, as ifP[x1] <= P[y]  K
, thenP[x2] <= P[x1] <= P[y]  K
buty  x2
is smaller. This implies that our candidatesx
foropt(y)
will have increasing values ofP[x]
. 
If
opt(y1) = x
, then we do not need to consider thisx
again. For if we find somey2 > y1
withopt(y2) = x
, then it represents an answer ofy2  x
which is worse (larger) thany1  x
.
Algorithm
Maintain a "monoqueue" of indices of P
: a deque of indices x_0, x_1, ...
such that P[x_0], P[x_1], ...
is increasing.
When adding a new index y
, we'll pop x_i
from the end of the deque so that P[x_0], P[x_1], ..., P[y]
will be increasing.
If P[y] >= P[x_0] + K
, then (as previously described), we don't need to consider this x_0
again, and we can pop it from the front of the deque.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.