# Minimum Size Subarray Sum

Leetcode 209. Minimum Size Subarray Sum

##### Problem

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 `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
```

Constraints:

• `1 <= target <= 109`
• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 105`

Follow up: If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.

##### Solution Approach – 1: Two Pointers

We can use two pointer approach to solve this problem. Please do not get confused with pointers of C or C++ or any other languages. Here, by pointer we simply mean index of the array.

Two pointer (or index) i and j will initially point to the first index of the given array. Then j will move forward and we will keep track of the summation of elements j passes. When summation will be >= target, we will move i forward until summation becomes < target. During this process of i’s movement, we will keep track of the length between i and j and save the minimum length.

###### C++ Code
```class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = nums.size();
if(len == 0)
return 0;
int i = 0;
int j = 0;
int sum_so_far = 0;
int min_subarray_length = INT_MAX;
// variable j will move forward and update sum_so_far
// variable i will wait at his position
while(j < len){
sum_so_far += nums[j];
/*
when sum_so_far is >= target, that length is a possible answer.
We will update our answer with that.
But, may be, if we eleminate zero or more element from the position of i,
sum_so_far might not be reduced that much to become < target.
So, we will try to eliminate elements from the position of i
and check if sum_so_far is still >= target or not.
*/
while(sum_so_far >= target && i <= j){
min_subarray_length = min(min_subarray_length, j - i + 1);
sum_so_far -= nums[i]; //eliminate the i-th element
i++; // and move i forward towards j
}
j++;
}
if(i == 0) // that measn, we never found sum_so_far to be >= target
return 0; //hence, there is no contiguous subarray and min_subarray_length = 0
return min_subarray_length;
}
};```
##### Conclusion

This is a medium level leetcode problem that can be solved using both two pointer and binary search approach. If you like the way we explained it, please write a comment. If you hate it, write comment as well. 🙂 There are other posts you may like listed below.

Happy Coding! 🙂