Approach 1: Sliding Window
We can rephrase this as a problem about the prefix sums of
P[i] = A + A + ... + A[i-1]. We want the smallest
y-x 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:
x1 < x2and
P[x2] <= P[x1], then
opt(y)can never be
x1, as if
P[x1] <= P[y] - K, then
P[x2] <= P[x1] <= P[y] - Kbut
y - x2is smaller. This implies that our candidates
opt(y)will have increasing values of
opt(y1) = x, then we do not need to consider this
xagain. For if we find some
y2 > y1with
opt(y2) = x, then it represents an answer of
y2 - xwhich is worse (larger) than
y1 - x.
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.
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.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.