Find length of shortest subarray with sum at least K (can have negatives).
Input: nums=[1], k=1 → Output: 1
Input: nums=[2,-1,2], k=3 → Output: 3
Prefix sums with monotonic deque. For each i, find last j where prefix[i]-prefix[j] >= K.
- Compute prefix sums
- Maintain increasing deque of indices
- For each i: while prefix[i]-prefix[deque.front] >= K record min and pop front
- While prefix[i] <= prefix[deque.back]: pop back (maintain increasing)
- Push i to deque
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
Deque<Integer> deque = new ArrayDeque<>();
int min = n + 1;
for (int i = 0; i <= n; i++) {
while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k)
min = Math.min(min, i - deque.pollFirst());
while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()])
deque.pollLast();
deque.addLast(i);
}
return min == n + 1 ? -1 : min;
}
- Time Complexity: O(n)
- Space Complexity: O(n)