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

Difficulty: interview

Starter code:

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def minSubArrayLen(self, k, nums):
         """
         :type k: int
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         _min = float('inf')
         _sum = 0
         j = 0
 
 
         for i ,n in enumerate(nums):
             _sum += n
             while _sum>=k:
                 _min = min(i-j+1, _min)
                 _sum -= nums[j]
                 j+=1
         return _min if _min!=float('inf') else 0
             


class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         result = float('inf')
         left = 0
         total = 0
         for i in range(len(nums)):
             total += nums[i]
             while total >= s:
                 result = min(result, i + 1 - left)
                 total -= nums[left]
                 left += 1
         return 0 if result == float('inf') else result 


class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         
         left, right, curr = 0, 0, 0
         minLen = len(nums)+1
         while right < len(nums):
             curr += nums[right]
             while curr >= s:
                 minLen = min(minLen, right-left+1)  
                 curr -= nums[left]
                 left += 1
             right += 1
         
         return minLen if minLen != (len(nums)+1) else 0

class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         i = 0
         j = 0
         _s = 0
         _min = len(nums) + 1
         if len(nums) == 0:
             return 0
         
         while(j < len(nums)):
             _s += nums[j]
             j += 1
             while(_s >= s):
                 _min = min(_min, j - i)
                 _s -= nums[i]
                 i += 1
                 
         if _min > len(nums): return 0
         else: return _min


class Solution:
 
     def minSubArrayLen(self, s, nums):
         total = left = 0
         result = len(nums) + 1
         for right, n in enumerate(nums):
             total += n
             while total >= s:
                 result = min(result, right - left + 1)
                 total -= nums[left]
                 left += 1
         return result if result <= len(nums) else 0

class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if sum(nums) < s:
             return 0
         
         res = float("inf")
         
         start = 0
         curr = 0
         
         for i in range(len(nums)):
             curr += nums[i]
             # print(i, curr)
             while curr >= s:
                 res = min(res, i - start + 1)
                 curr -= nums[start]
                 start += 1
         
         return res
                 


class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         total = left = 0
         result = len(nums) +1
         for right,num in enumerate(nums):
             total += num
             while total>=s:
                 result = min(result,right-left+1)
                 total -= nums[left]
                 left += 1
         return result if result <= len(nums) else 0
                 
             
         


class Solution:
     # this one is really easy to confuse you to apply greedy method. The greed method will start from the whole string and delete the smaller one of the start and the end element. This is wrong since there could be a case that at one end there are two mid-range number that sum over s while at the other end there are a big number and a smalle one which do not sum over s. The greedy method will delete the first mid-range number hence provide the wrong answer.
     
     # instead, one could apply the following algorithm: start from the beginning, add nums[i] to sum, if sum is greater than s, we keep substracting from the beginning of the current subarray until the sum is no greater thans, then we keep moving i to the next one unitl the sum is greater than s again. 
     def minSubArrayLen(self, s, nums): 
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if not nums or sum(nums)<s:
             return 0
         ans=len(nums)
         left=0
         temps=0
         for i in range(len(nums)):
             temps+=nums[i]
             while temps>=s:
                 ans=min(ans,i+1-left)
                 temps-=nums[left]
                 left+=1
         return ans


class Solution:
     def minSubArrayLen(self,s,nums):
         """two pointers. 在一个循环完成后,[i-1,j]必然是[0,j]中最短的
         符合要求的区间. 故i-1前作为起点,j前作为终点的区间可不考虑,
         即截掉i-1之前的区间."""
         i=0;
         j=0;
         tempSum=0;
         length=len(nums);
         minLength=0x7FFFFFFF;
         while(i<length and j<length):
             while j<length:
                 tempSum+=nums[j];
                 if tempSum>=s:
                     break;
                 j+=1;
             if j<length:
                 minLength=min(j-i+1,minLength);
                 while i<=j:
                     if tempSum<s:
                         break;
                     tempSum-=nums[i];
                     i+=1;
 
                 minLength=min(j-i+2,minLength);
                 j+=1;
                     
 
         if minLength==0x7FFFFFFF:
             return 0;
         else:
             return minLength;


class Solution(object):
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         import math
         minlen = math.inf
         pt1 = 0
         pt2 = 0
         cursum = nums[0]
         while pt2 < len(nums):
             if cursum >= s:
                 minlen = min(minlen,pt2 - pt1 + 1)
             if minlen == 1:
                 return 1
             if cursum < s:
                 pt2 += 1
                 if pt2 < len(nums):
                     cursum += nums[pt2]
             elif cursum >= s:
                 cursum -= nums[pt1]
                 pt1 += 1
         return 0 if minlen == math.inf else minlen

class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if sum(nums) < s:
             return 0
         
         res = float("inf")
         
         start = 0
         curr = 0
         
         for i in range(len(nums)):
             curr += nums[i]
             # print(i, curr)
             while curr >= s:
                 res = min(res, i - start + 1)
                 curr -= nums[start]
                 start += 1
         
         return res
                 


class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         
         
         prePtr = 0
         curPtr = 0
         
         curSum = 0
         
         res = float('inf')
         
         while curPtr < len(nums):
             
             curSum += nums[curPtr]
                 
             if curSum >= s:
                     
                 while curSum >= s:
                     curSum -= nums[prePtr]
                     prePtr += 1
                 prePtr -= 1
                 curSum += nums[prePtr]
                     
                 res = min(res, curPtr-prePtr+1)
                 
             curPtr += 1
         if res == float('inf'):
             return 0
         else:
             return res


class Solution:
     def minSubArrayLen(self, s, nums):
         """
         :type s: int
         :type nums: List[int]
         :rtype: int
         """
         if nums is None or len(nums) == 0:
             return 0
         running_sum = [nums[0]]
         for num in nums[1:]:
             running_sum.append(running_sum[-1] + num)
         def sub_sum(i,j):
             to_remove = 0 if i == 0 else running_sum[i-1]
             to_add = 0 if j == 0 else running_sum[j-1]
             return to_add - to_remove
         min_seen = float('inf')
         fast = 0
         slow = 0
         while fast < len(nums):
             while sub_sum(slow, fast) < s and fast < len(nums):
                 fast += 1
             while sub_sum(slow, fast) >= s and slow <= fast:
                 min_seen = min(min_seen, fast - slow)
                 slow += 1
         return 0 if min_seen == float('inf') else min_seen