Shortest Subarray with Sum at Least K
Problem
Return the length of the shortest non-empty contiguous subarray whose sum is at least k, or −1 if none exists. The array can contain negative numbers.
Example 1
Input: nums = [2, -1, 2], k = 3 Output: 3
Example 2
Input: nums = [1, 2], k = 4 Output: -1
Test cases
Case 1
Input: [1], 1 Expected: 1
Case 2
Input: [1,2], 4 Expected: -1
Case 3
Input: [2,-1,2], 3 Expected: 3
Case 4
Input: [84,-37,32,40,95], 167 Expected: 3
View solutionHide solution1 approach
1. Prefix sums + monotonic deque
Time O(n)Space O(n)
Keep candidate start prefixes in increasing order. While the current prefix minus the front is ≥ k, record and drop the front (it cannot do better later). Drop back entries ≥ current prefix — a later, smaller start is always better. Negatives are why a plain sliding window fails.
function shortestSubarray(nums, k) { const n = nums.length, pre = [0]; for (const x of nums) pre.push(pre[pre.length - 1] + x); const dq = []; let head = 0, best = Infinity; for (let i = 0; i <= n; i++) { while (head < dq.length && pre[i] - pre[dq[head]] >= k) best = Math.min(best, i - dq[head++]); while (dq.length > head && pre[dq[dq.length - 1]] >= pre[i]) dq.pop(); dq.push(i); } return best === Infinity ? -1 : best;}