Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1], k = 1 Output: 1
Example 2:
Input: nums = [1,2], k = 4 Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3 Output: 3
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= k <= 109class Solution {
public int shortestSubarray(int[] nums, int targetSum) {
int n = nums.length;
// Size is n+1 to handle subarrays starting from index 0
long[] prefixSums = new long[n + 1];
// Calculate prefix sums
for (int i = 1; i <= n; i++) {
prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
}
Deque<Integer> candidateIndices = new ArrayDeque<>();
int shortestSubarrayLength = Integer.MAX_VALUE;
for (int i = 0; i <= n; i++) {
// Remove candidates from front of deque where subarray sum meets target
while (
!candidateIndices.isEmpty() &&
prefixSums[i] - prefixSums[candidateIndices.peekFirst()] >=
targetSum
) {
// Update shortest subarray length
shortestSubarrayLength = Math.min(
shortestSubarrayLength,
i - candidateIndices.pollFirst()
);
}
// Maintain monotonicity by removing indices with larger prefix sums
while (
!candidateIndices.isEmpty() &&
prefixSums[i] <= prefixSums[candidateIndices.peekLast()]
) {
candidateIndices.pollLast();
}
// Add current index to candidates
candidateIndices.offerLast(i);
}
// Return -1 if no valid subarray found
return shortestSubarrayLength == Integer.MAX_VALUE
? -1
: shortestSubarrayLength;
}
}