Shortest Reaching Subarray (Negatives)

Difficulty: 2200 5000 ms 128 MB

prefix-sums deque

Values may be negative. Find the length of the shortest contiguous subarray with sum at least K, or −1.

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

Output: the minimum length, or −1.

Constraints:

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

Sample Tests

5 3
2 -1 2 -3 4

1

3 100
1 2 3

-1

Read the Editorial