706. The Shortest Stretch That Reaches k, Negatives Allowed
Print the length of the SHORTEST contiguous stretch whose total is at least k, or -1 if
no stretch reaches it. Values may be negative.
2 -1 2, k = 3 -> 3
-5 10, k = 5 -> 1
84 -37 32 40 95, k = 167 -> 3
1 2, k = 4 -> -1
## Why problem 681 does not transfer
681 asks the same question with POSITIVE values, and there the running total rises with the window, so shrinking from the left is safe. Here it is not.
On 2 -1 2 with k = 3 a window reaching the target may have to CONTAIN a stretch that falls
short. The shrink rule has nothing to test, and the left edge cannot be moved forward without
possibly discarding the answer.
That the two problems differ only in a sign, and that the sign destroys the method, is the point of putting them side by side.
## Prefix totals turn it into a search over pairs
Let P[0] = 0 and P[i] = a[0] + ... + a[i-1]. The stretch from i to j-1 totals
P[j] - P[i], so the question is: for each j, find the LARGEST i < j with
P[j] - P[i] >= k
and the answer is the smallest j - i.
## The deque, and the two reasons an index is dropped
Keep a deque of indices whose prefix totals INCREASE from front to back.
· From the front. If P[j] - P[front] >= k, that front index gives a valid stretch.
Record j - front and remove it: any later j pairs with it to give a LONGER stretch, so
it can never help again.
· From the back. Before pushing j, drop every back index with P[back] >= P[j]. Such an
index sits further left AND has a total at least as large, so for every future j it is
beaten by j on both counts.
Both removals are permanent, each index enters and leaves once, and the sweep is linear.
## Why the deque stays increasing
The back rule is exactly the rule that maintains it. That is not a coincidence: the discarded indices are the ones that could never be the best left end, and dropping them is what makes the front of the deque meaningful.
## Sweeping over n + 1 prefixes, not n
The loop runs over P[0] .. P[n]. Starting at P[1] loses every stretch that begins at index
0, and 5 with k = 5 is the one-line test for it.
## Overflow
200000 values of magnitude up to 10^4 give prefix totals up to 2 * 10^9 in either
direction, and k can be 10^9.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^4 ≤ each value ≤ 10^4` - `-10^9 ≤ k ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers, which may be negative.
Output
Print one integer, the shortest qualifying length, or -1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.