Minimum Size Subarray Sum
Solution: Using Sliding Window
We can use variable sized Sliding Window Pattern to solve this problem.
Step 1
Assuming the targetSum
= 7.

windowSum
is still less than targetSum
i.e. 1 < 7
, continue to expand the window.
Step 2

windowSum
is still less than targetSum
i.e. 5 < 7
, continue to expand the window.
Step 3

windowSum
is still less than targetSum
i.e. 6 < 7
, continue to expand the window.
Step 4

windowSum
is now greater than or equal to targetSum
i.e. 8 >= 7
. At this point, we should store this window size as one of the answers.
Now, we should shrinking this window and look if any smaller window is present.
Step 5

After shrinking the window, the windowSum
has become 7, which is still greater than or equal to targetSum
. Hence, we have found a better answer. Therefore, update minLength
to current window size which is 3.
Step 6

After shrinking the window one more time, we have got windowSum
smaller to targetSum
which means an invalid window. Hence, now we would start expanding the window again to find a better answer.
Step 7

After expanding window, we have again got windowSum
greater than or equal to targetSum
. Let's update the minLength
. But the minLength
is already 3 so it won't get updated.
As a next step, we will try to shrink the window again from the left side in order to find the minLength
.
Step 8

After shrinking the window, we have got an invalid window again. So, let's try expanding it again.
Step 9

After expanding window, we have again got windowSum
greater than or equal to targetSum
. Let's update the minLength
. But the minLength
is already 3 so it won't get updated.
As a next step, we will try to shrink the window again from the left side in order to find the minLength
.
Step 10

Even after shrinking the window, the windowSum
has become 7, which is still greater than or equal to targetSum
. Hence, we have found a better answer. Therefore, update minLength
to current window size which is 2.
As a next step, we will try to shrink the window again from the left side in order to find the minLength
.
Step 11

After shrinking the window, we have got an invalid window again. So, let's try expanding it again.
Step 12

The loop will be terminated here, hence return minLength
.
Let's look at the code now.
Java Code
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int windowStart = 0;
int windowSum = 0;
int minLength = Integer.MAX_VALUE;
for(int windowEnd = 0; windowEnd < nums.length; windowEnd++) {
windowSum += nums[windowEnd];
while(windowSum >= target) {
minLength = Math.min(minLength, windowEnd - windowStart + 1);
windowSum -= nums[windowStart];
windowStart += 1;
}
}
return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
}
C++ Code
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int windowStart = 0;
int windowSum = 0;
int minLength = INT_MAX;
for(int windowEnd = 0; windowEnd < nums.size(); windowEnd++) {
windowSum += nums[windowEnd];
while(windowSum >= target) {
minLength = min(minLength, windowEnd - windowStart + 1);
windowSum -= nums[windowStart];
windowStart += 1;
}
}
if(minLength == INT_MAX) return 0;
else return minLength;
}
};
Python Code
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
windowStart = 0
windowSum = 0
minLength = math.inf
for windowEnd in range(len(nums)):
windowSum += nums[windowEnd]
while(windowSum >= target):
minLength = min(minLength, windowEnd - windowStart + 1)
windowSum -= nums[windowStart]
windowStart += 1
return 0 if minLength == math.inf else minLength
Complexity Analysis
Time Complexity: O(N), where N is the size of the array nums
.
Space Complexity: O(1)