# 209. Minimize Size Subarray Sum

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