Shortest Subarray With Sum At Least K

Given an array of N integers (which may be negative, zero, or positive) and an integer K, find the length of the shortest contiguous subarray whose sum is greater than or equal to K. If no such subarray exists, print -1. Solve the problem efficiently using prefix sums combined with a monotonic deque, rather than checking every subarray.

Input: The first line contains two integers N and K. The second line contains N space-separated integers, the array. Output: Print a single integer: the length of the shortest subarray with sum at least K, or -1 if none exists.

1 <= N <= 100000, -100000 <= arr[i] <= 100000, -10^9 <= K <= 10^9

This is a great example of recognizing when a simpler technique (plain sliding window) DOESN'T apply due to a relaxed constraint (negative numbers allowed) - and reaching for the more general prefix-sum-plus-monotonic-deque technique instead.

Find the shortest contiguous subarray (allowing negative numbers) whose sum is at least a given target K. Brute force: Check every possible contiguous subarray directly, summing each and tracking the shortest one meeting the target - this costs O(n²), too slow for large arrays, especially since negative numbers rule out simpler sliding-window techniques that require all-positive values. Optimised: Since values can be NEGATIVE, a plain sliding window (which relies on sums only increasing as the window grows) doesn't work here - but maintaining a deque of prefix-sum indices in STRICTLY INCREASING order lets you find, for each ending point, the BEST possible starting point efficiently, since any 'dominated' earlier index (with an equal-or-larger prefix sum than a later one) can never be optimal and is safely discarded.

1. Build a PREFIX SUM array, so the sum of the subarray from index i+1 to j equals prefix[j] - prefix[i] - you want the SMALLEST (j - i) with that difference at least K. 2. Maintain a deque of indices with STRICTLY INCREASING prefix-sum values. 3. Whenever prefix[j] minus the prefix sum at the FRONT index already reaches K, record the length and pop that front index (it can never produce a better answer again); before adding index j to the BACK, pop any back index whose prefix sum is >= prefix[j] (a later index with an equal-or-smaller prefix sum always dominates it).

Time: O(n) - each index is pushed and popped from the deque at most once. Space: O(n) in the worst case, for the deque and prefix sum array.

If every element is negative and K is positive, no subarray can qualify, so the answer is -1; a single element already meeting K on its own gives an answer of 1.

Be ready to explain clearly why this problem, unlike 'Smallest Subarray With Sum Greater Than X' (positive-only values), CANNOT use a simple two-pointer sliding window - the presence of negative numbers breaks the monotonic growth assumption that sliding windows rely on.