Shortest Subarray with Sum at Least K

Problem

Sensor batches need the shortest contiguous stretch of readings whose sum reaches a quality threshold - and readings can be negative when a sensor recalibrates. Given an integer array and a threshold k, return the length of the shortest non-empty subarray with sum at least k, or -1 when none exists.

Example 1:

Input: nums = [3, 1, 4, 1, 5], k = 7
Output: 3
Explanation: no window of length 2 reaches 7 (the best is [1, 5] at index 3, summing 6); the length-3 window [3, 1, 4] sums 8 >= 7, so the shortest length is 3.

Example 2:

Input: nums = [2, -1, 4], k = 5
Output: 3
Explanation: no two-element window reaches 5; the full array sums 5 exactly.

Example 3:

Input: nums = [1, 2], k = 4
Output: -1
Explanation: the entire array sums to 3 - no window qualifies.

Constraints:

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9

Solution Breakdown

Approach - prefix sums with a monotonic deque of candidate left edges.

The textbook sliding window dies on negatives: its two-pointer logic assumes growing the window only grows the sum, so shrinking from the left when the sum clears k is always safe. A negative element breaks that - extending can reduce the sum, so a window that fails now might succeed after absorbing more elements, which the two-pointer rule never revisits. The repair is to reframe on prefix sums: prefix[r] - prefix[l] is the sum of [l, r), so for each right edge r you want the latest left edge l whose prefix is at most prefix[r] - k, minimizing r - l. Candidates for l live in a deque kept strict-increasing in prefix value. Two eviction rules make the walk linear. From the front: while the oldest candidate's headroom reaches k, it starts a valid window - record its length and pop it; any window that same candidate could start with a later r is strictly longer, so it is spent. From the back: before pushing r, pop every candidate whose prefix is >= prefix[r] - it is dominated on both axes (less headroom and an earlier start than r offers), so no future right edge will ever prefer it.

Trace [3, 1, 4, 1, 5], k = 7: prefix [0, 3, 4, 8, 9, 14]. At r = 3 (prefix 8): 8 - 0 = 8 >= 7 records length 3 and pops index 0; 8 - 3 = 5 falls short. At r = 4 (prefix 9): 9 - 3 = 6, no. At r = 5 (prefix 14): 14 - 4 = 10 >= 7 records 3 again; 14 - 8 = 6 stops. Answer 3. The negative-heavy case [2, -1, 4], k = 5: prefix [0, 2, 1, 5] - the dip at index 2 (prefix 1) evicts nothing yet fails to qualify, and only the full array's prefix[3] - prefix[0] = 5 lands, length 3.

Edge cases - an input whose total is below k never records a window and returns -1 ([1, 2] with k = 4); a single qualifying element gives length 1 ([5], k = 5, via prefix[0] = 0 enabling the full-prefix window); strictly decreasing prefixes (all-negative runs) leave the deque growing, which is correct - no candidate ever dominates another.

Complexity - O(n) time: one prefix pass, then each index enters the deque exactly once and leaves at most once - every while-loop iteration is paid by a pop, so the total is linear. O(n) space for the prefix array and the deque. Without negatives, the plain two-pointer window is simpler and also O(n); the deque is the price negatives extract.