Data structures and algorithms
## Minimum Size Subarray Sum

###### Example 1:

###### Example 2:

###### Example 3:

###### Constraints:

##### Solution:

###### Time/Space Complexity:

###### Explanation:

comments powered by Disqus

**Minimum Size Subarray Sum:**
Given an array of positive integers `nums`

and a positive integer `target`

, return the **minimal length** of a subarray whose sum is greater than or equal to `target`

. If there is no such subarray, return `0`

instead.

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

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

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

`1 <= target <= 10^9`

`1 <= nums.length <= 10^5`

`1 <= nums[i] <= 10^4`

Try this Problem on your own or check similar problems:

- Minimum Operations to Reduce X to Zero
- K Radius Subarray Averages
- Maximum Product After K Increments

```
public int minSubArrayLen(int target, int[] nums) {
int minLength = nums.length + 1, i = 0, j = 0, windowSum = 0;
while(j < nums.length){
windowSum += nums[j++];
while(windowSum >= target){
minLength = Math.min(minLength, j - i);
windowSum -= nums[i++];
}
}
return minLength % ( nums.length + 1);
}
```

- Time Complexity:
*O(n)* - Space Complexity:
*O(1)*

Implementation uses **sliding window** approach where we have two pointers `i`

and `j`

respectively pointing to the start and end of our window. When the window is valid, we can check if we are improving on one of the desired properties given by problem statement. In our problem a window is valid when the sum of all elements in the window are greater or equal to the target, and the property we’re looking to optimize is the length (shorter lengths are desired by the problem statement since we’re looking for the shortest subarray fulfilling the requirement). So, we move the end `j`

of our window to the right therefore expanding the window and each time we check if the current window is fulfilling the requirement `windowSum >= target`

(we’re tracking the `windowSum`

so we can check if window is valid). If the window is valid, we try to shorten it by moving our start `i`

to the right thus reducing the window length and we do that until the shortening breaks the requirement (invalidates the window). We’re keeping track of the shortest window fulfilling the requirement and finally we return `minLength`

(with a trick to return `0`

if there is no subarray/window with sum greater or equal to the `target`

).

Don’t settle for anything less than the crown. Join our newsletter and become the King of Interviews! **Click here** to join now and get the latest updates.