Shortest Subarray with Sum at Least K

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}