Shortest Subarray With Sum at Least K
hardArrays & Prefix Sums+40 XPTime limit 2s
Find the length of the shortest non-empty contiguous subarray whose sum is at least k. The array may contain negative numbers, so a simple sliding window does not work.
Input:
- line 1:
n k - line 2:
nintegers
Output: the shortest length, or -1 if no subarray reaches k.
Constraints: 1 ≤ n ≤ 10⁵, −10⁵ ≤ a[i] ≤ 10⁵, 1 ≤ k ≤ 10⁹.
Think about it: with prefix sums, you want j > i with P[j] − P[i] ≥ k and j − i small. Keep a deque of indices with increasing prefix sums. For each new j: pop from the front while P[j] − P[front] ≥ k (each popped start has found its best end); then pop from the back every index whose prefix is ≥ P[j] — a later, smaller start is always better.
Sample input 1
3 3 2 -1 2
Sample output 1
3
Sample input 2
2 4 1 2
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).