Minimum Size Subarray Sum
Medium · Sliding Window · Array · Binary Search · Sliding Window · Prefix Sum
Problem
You are given an array of positive integers nums and a positive integer target. Return the length of the shortest contiguous subarray whose sum is at least target.
If no subarray reaches target, return 0.
Examples
Input: target = 8, nums = [3,1,5,2,6] Output: 2
[2,6] sums to exactly 8, and no single value reaches 8.
Input: target = 20, nums = [1,2,3] Output: 0
Even the whole array only sums to 6.
Input: target = 11, nums = [1,2,3,4,5] Output: 3
[3,4,5] sums to 12. Every pair sums to at most 9.
Constraints
- 1 <= target <= 10^9
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^4
Approaches
- Baseline: every start, extend until it reaches the target — time O(n²), space O(1)
Follow-up
What if nums may hold negative values? The window sum stops being monotonic, so the two-pointer walk fails. Prefix sums with a monotonic deque of candidate starts still solve it in O(n): see the use case “Shortest window when values can be negative”.
Related problems
Start free on Cariara · Coding problems · System design studio
