31. Smallest Subarray With Sum Greater Than a Given Value

Given an array of positive integers and a value x, find the length of the smallest contiguous subarray whose sum is strictly greater than x. If no such subarray exists, print -1.

Input: The first line contains two integers n and x. The second line contains n space-separated positive integers. Output: Print a single integer - the length of the smallest subarray with sum strictly greater than x, or -1 if none exists.

1 <= n <= 10^5, 1 <= arr[i] <= 10^4

The 'grow then shrink' two-phase movement within a single pass (rather than two separate passes) is what keeps this O(n) instead of O(n²) - each element is added to the window and removed from it at most once across the whole run.

Find the shortest contiguous stretch of a (positive-only) array whose total sum is strictly more than a given value. Brute force: Check every possible contiguous subarray directly, summing each one and tracking the shortest one exceeding the target - this costs O(n²) or worse, too slow for large arrays. Optimised: Because every value is POSITIVE, growing the window always increases the sum and shrinking it always decreases the sum - this monotonic behavior is exactly what makes a sliding window valid: you never need to reconsider a window you've already shrunk past, so the two pointers only ever move forward, giving a linear total amount of work.

Maintain a window [left, right] and its running sum: expand right one step at a time adding to the sum, and whenever the sum exceeds x, record the window length and shrink from the left (subtracting elements) as long as the sum still exceeds x, since shrinking can only help find a smaller valid window. Because every element is positive, the sum changes monotonically as either pointer moves, so each pointer only ever moves forward, giving a total of O(n) pointer movements instead of any per-position search. Time: O(n) Space: O(1)

Check every contiguous subarray by summing its elements directly, and among all subarrays whose sum exceeds x, keep track of the shortest length found. This is a straightforward exhaustive check of all O(n^2) subarrays with an O(n) sum computation for each. Time: O(n^3) Space: O(1)

Build a prefix sum array; since all elements are positive, the prefix sums are strictly increasing, so for each starting index the smallest ending index whose prefix sum exceeds x + prefixSum[start-1] can be located with binary search instead of a linear scan. This cuts the inner search from O(n) to O(log n) for each of the n starting positions. Time: O(n log n) Space: O(n)

1. Grow a window from the left by adding elements from the right, keeping a running sum. 2. The moment the running sum exceeds the target, try shrinking the window from the LEFT as much as possible while the sum still stays above the target - each successful shrink is a shorter valid window, worth recording if it's the smallest so far. 3. Once shrinking would drop the sum back to or below the target, stop shrinking and resume growing from the right. 4. Track the smallest valid window length found throughout this entire process.

Time: O(n) - both pointers only ever move forward, so the total combined movement across the whole algorithm is linear. Space: O(1) - just a running sum and window boundary trackers.

Test n = 1, n = 10^5 for performance, and cases where no subarray's sum exceeds x (should print -1).

Be explicit that this sliding-window technique ONLY works because every value is guaranteed positive - if negative values were allowed, growing or shrinking the window wouldn't reliably increase or decrease the sum, and the technique would break down entirely.