Minimum Size Subarray Sum — Problem Statement & Solution Guide
Problem Description
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Examples
Input
[2,3,1,2,4,3], target = 7
Output
2
Explanation: Step-by-step: with input [2,3,1,2,4,3] and target 7, we find the subarray [4,3] which has a sum of 7, thus the minimal length is 2.
Input
[1,4,4], target = 4
Output
1
Explanation: Step-by-step: with input [1,4,4] and target 4, we find the subarray [4] which has a sum of 4, thus the minimal length is 1.
Constraints
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
Optimal Approach & Strategy
Use a two-pointer sliding window approach. Maintain a running window sum. Expand the right pointer; when window sum >= target, update min length and shrink from left until sum < target. Time Complexity: O(n), Space Complexity: O(1).
Brute Force Approach
Check all possible contiguous subarrays, calculate their sums, and find the minimum length of a subarray whose sum is >= target. Time Complexity: O(n^2), Space Complexity: O(1).
Step-by-Step Dry Run
Input: target = 7, nums = [2,3,1,2,4,3] Right = 0: sum = 2 Right = 1: sum = 5 Right = 2: sum = 6 Right = 3: sum = 8 >= 7 -> minLen = 4, shrink left -> sum = 6 Right = 4: sum = 10 >= 7 -> minLen = 4, shrink left -> sum = 7 >= 7 -> minLen = 3, shrink left -> sum = 6 Right = 5: sum = 9 >= 7 -> shrink left -> minLen = 2, shrink left -> sum = 3. Result: 2
Verified Code Solutions
function minSubArrayLen(nums, target) {
let left = 0, currSum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
}class Solution {
public:
int minSubArrayLen(vector<int>& nums, int target) {
int left = 0, currSum = 0, minLen = INT_MAX;
for (int right = 0; right < nums.size(); right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, currSum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}def minSubArrayLen(nums, target):
left, curr_sum, min_len = 0, 0, float('inf')
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= target:
min_len = min(min_len, right - left + 1)
curr_sum -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenfunction minSubArrayLen(nums, target) {
let left = 0, currSum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= target) {
minLen = Math.min(minLen, right - left + 1);
currSum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.