Minimum Size Subarray Sum [Medium] — Shrinkable Sliding Window
Sanjeev SharmaAdvertisement
Problem Statement
Find the minimal length contiguous subarray with sum >= target. Return 0 if none exists.
Input: target=7, nums=[2,3,1,2,4,3] → Output: 2 ([4,3])
Intuition
Expand right pointer. Once sum >= target, record window size and shrink from the left — this is the "shrinkable window" pattern.
Solutions
C++
int minSubArrayLen(int target, vector<int>& nums) {
int left=0,sum=0,ans=INT_MAX;
for(int right=0;right<nums.size();right++){
sum+=nums[right];
while(sum>=target){ans=min(ans,right-left+1);sum-=nums[left++];}
}
return ans==INT_MAX?0:ans;
}
Java
public int minSubArrayLen(int target, int[] nums) {
int left=0,sum=0,ans=Integer.MAX_VALUE;
for(int right=0;right<nums.length;right++){
sum+=nums[right];
while(sum>=target){ans=Math.min(ans,right-left+1);sum-=nums[left++];}
}
return ans==Integer.MAX_VALUE?0:ans;
}
Python
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = s = 0
ans = float('inf')
for right, val in enumerate(nums):
s += val
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]; left += 1
return 0 if ans == float('inf') else ans
Complexity
- Time: O(n)
- Space: O(1)
Advertisement
