Minimum Size Subarray Sum
The key idea
Because every value is positive, the running sum of a window grows when you add to the right and shrinks when you drop from the left. So you can grow the window until it reaches
target, then shrink it from the left as far as still valid, recording the smallest length — each index enters and leaves the window at most once.Problem
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
A subarray is a contiguous, non-empty sequence of elements within nums. Because all values are positive, adding a later element only increases a window's sum, which is the property the optimal scan relies on.
As a follow-up, if you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Constraints
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4
Examples
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Input: target = 4, nums = [1,4,1,4,7]
Output: 1
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD