Minimum Size Subarray Sum
Description
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The subarray [4, 3] has sum = 7 >= target and is the shortest with length 2.
Example 2:
Input: target = 4, nums = [1, 4, 4]
Output: 1
Explanation: The subarray [4] (either one) has sum = 4 >= target with length 1.
Example 3:
Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
Explanation: The entire array sums to 8, which is less than 11. No valid subarray exists.
Constraints
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Sliding window with variable size
- Approach
- Use two pointers (left, right). Expand right to grow window sum. When sum >= target, record length and shrink from left to find minimum.
- Complexity
- Expand window until sum >= target, then shrink from left while maintaining validity
Solutions
Show PY Solution
def solution(target, nums):
count = float("inf")
curr = 0
left = 0
for right in range(len(nums)):
curr += nums[right]
while curr >= target:
count = min(count, right - left + 1)
curr -= nums[left]
left += 1
return 0 if count == float("inf") else count