Shortest Sufficient Stretch

Difficulty: 1500 3000 ms 128 MB

sliding-window two-pointers

Values are positive. Find the length of the shortest contiguous stretch whose sum is at least K, or −1 if no stretch reaches K.

Input: the first line has N and K; the second line has N positive integers.

Output: the minimum length, or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 10⁴
• 1 ≤ K ≤ 10⁹

Sample Tests

6 7
2 3 1 2 4 3

2

3 100
1 2 3

-1

Read the Editorial