# Minimum Size Subarray Sum | Sliding Window

Find the minimum size subarray with sum greater than or equal to the target. Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to the 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 the minimal length under the problem constraint.
```

Example 2:

```Input: target = 4, nums = [1,4,4]
Output: 1
```

Example 3:

```Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
```

### Approach:

Subarrays are arrays within another array. Subarrays contain a contiguous set of elements.

Consider an array {1,2,3,4}

List of all its subarrays are `{},{1},{2},{3},{4},{1,2},{2,3},{3,4},{1,2,3,4}`

We have to find a minimum size sub-array with a sum greater than or equal to the target. One approach would be to generate all the sub-arrays and find the subarray with minimal size and sum >= target. Of course, this is a very inefficient approach. So instead of that, we will use Sliding Window Approach.

Sliding Window is a window that moves through the array. Elements within that window are considered as a subarray. We calculate the sum of elements inside the array and check if it is greater than or equal to the target. The sliding window moves from left to right.  At each step 1 element go out and 1 element goes inside the window.

Slide Explanation:      Screenshot (14)
Screenshot (15)
Screenshot (16)
Screenshot (17)
Screenshot (19)
Screenshot (18)  ### Algorithm:

• Initially, the size of the sliding window is 1.
• Keep adding elements inside the window until we get the sum >= target
• When the target is reached, calculate window size and check if it is the minimum size.
• Now Keep removing elements until the sum < target.

### Program:

```class Solution {
public int minSubArrayLen(int target, int[] nums) {
int size = nums.length;
int sum = 0,start = 0;
boolean reachedTarget = false;
for(int end = 0; end<nums.length; end++)
{
//increase windowsize
sum += nums[end];
if(sum >= target)
{
reachedTarget = true;
size = Math.min(size, end-start+1);
}

//shrink till we get sum lesser than target
while(sum >= target )
{
//while decreasing also update minSize
size = Math.min(size, end-start+1);
sum -= nums[start];
start++;
}

}
return reachedTarget ? size : 0;  //sum not reached the target.
}
}

```

### Complexity

Time Complexity – O(n) since we traverse the input array only once

Space Complexity – O(1) since we are not using any extra space

### You Might Also Like…

To find maximum of the numbers under Sliding Window

Check if single swap can make strings equal ### Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation. 