MediumNeetCode150ArrayBinary SearchSliding WindowPrefix Sum
Minimum Size Subarray Sum
Find minimal length subarray with sum >= target.
Examples
Input
target = 7, nums = [2,3,1,2,4,3]
Output
2
[4,3] has length 2.
Constraints
- •
1 <= target <= 10^9 - •
1 <= nums.length <= 10^5 - •
1 <= nums[i] <= 10^5
Approaches
Check all subarrays.
CodeT: O(n^2) | S: O(1)
Expand then shrink.
CodeT: O(n) | S: O(1)
Same approach.
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all subarrays. |
| Sliding Window | O(n) | O(1) | Expand then shrink. |
| Sliding Window Optimized | O(n) | O(1) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Check all subarrays.
Sliding Window
T: O(n)S: O(1)
Expand then shrink.
Sliding Window Optimized
T: O(n)S: O(1)
Same approach.
Common Mistakes
Not handling no valid subarray
Off-by-one in window
Wrong sum calculation