189. Minimum Size Subarray Sum
You get a positive integer target and an array nums of positive integers.
Your function receives target and nums, and returns the length of the shortest contiguous run of elements whose sum reaches target or more. If even the whole array falls short, return 0.
Because every element is positive, growing a window only ever raises its sum and shrinking it only ever lowers it — that monotonicity is the key to beating the obvious quadratic scan.
Example 1:
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The two-element run [4, 3] sums to 7. No single element reaches 7, so 2 is the minimum.
Example 2:
Input: target = 4, nums = [1, 4, 4]
Output: 1
Explanation: A single 4 already meets the target on its own.
Example 3:
Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
Explanation: All eight elements together sum to 8, still below 11, so no valid subarray exists.
Constraints:
- 1 ≤ target ≤ 10⁹
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁴
Hints:
For a fixed start index, the sum only grows as you extend the end — so once it reaches target you can stop extending. That early break gives a decent O(n²) baseline.
All elements are positive, so prefix sums are strictly increasing. "Shortest run starting at i" becomes a binary search for the first prefix value >= prefix[i] + target: O(n log n).
Better still, keep one window [left, right]: push right forward adding elements, and whenever the window's sum is >= target, record its length and pull left forward to shrink. Each index enters and leaves the window once — O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Expected output: 2