## Problem

Given an array of n positive integers and a positive integer s, find the minimal length of a **contiguous** subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

```
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
```

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

## Thought Process

- loop thru the array, if sum >= s exits, return 1
- create a window, for window of length from 2 to n
- if sum >= s, return window length
- loop thru to window length of n

- return 0, if no such window is found

## White Board

Below is the white board:

## Code

```
class Solution:
def msa(self, nums, s):
temp = []
for i in range(len(nums)):
for j in range(len(nums)):
if sum(nums[i:j+1]) >= s:
temp.append(len(nums[i:j+1]))
if temp:
return min(temp)
return 0
def test_msa():
nums = [1,2,3,4,5]
s = 15
msa = Solution().msa(nums, s)
print(msa)
test_msa()
```

```
5
```

## Complexity

- This brute force solution has a time complexity of O(n**3), as will loop thru all sub-arrays via two pointers O(n**2), within each iteration, sum an array is also O(n)
- The space complexity is O(n), as I created a space temp

Even the result is correct but it will not pass lc as the max time is reached.

## Optimization

The brute force solution wasted to many resources on constantly calculating sums of all sub-arrays

```
class Solution2:
def msa_2(self, nums, s):
l, r = 0, -1
# nums[l:r], initially empty
sum = 0
res = len(nums) + 1
# impossible to reach, an invalid result
while(l < len(nums)):
if (sum < s) and (r + 1 < len(nums)):
# if sum is smaller, keep moving right index to increase window
r += 1
sum += nums[r]
else:
# if sum >= s, move left index to shrink window
sum -= nums[l]
l += 1
if sum >= s:
# if sum is found
res = min(res, r - l + 1)
# r - l + 1 as the segment are close on both end
if(res == len(nums) + 1):
# if no solution is found
return 0
return res
def test_msa2():
nums = [1,2,3,4,5]
s = 15
msa2 = Solution2().msa2(nums, s)
print(msa2)
test_msa()
```

```
5
```

Time complexity is O(n), as only did one round of iteration; Space complexity is O(1) since no new space is used