## 209.Minimum Size Subarray Sum (positive integer)

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

Thoughts:

1. O(n): Having a left and right pointer, Scan through the array, if record the sum if arr[i...j] >=s, then compare min with current sum, then try to move left pointer up, then compare with min again.
2. O(nlogn) Binary Search:

Code: O(n):

``````class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums == null || nums.length == 0 ) return 0;

int i = 0, j = 0 , sum = 0 , min = Integer.MAX_VALUE;
while(j < nums.length){
sum += nums[j++];
while(sum >=s){
min = Math.min(min, j - i); //(old j) - i + 1 = j - i
sum -= nums[i++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
``````

Code: Another C++

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
while (j < nums.length) {
while (sum < s && j < nums.length) sum += nums[j++];
if(sum>=s){
while (sum >= s && i < j) sum -= nums[i++];
min = Math.min(min, j - i + 1);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
``````

Python

``````class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
i, j, pres, res = 0 , 0 , 0, len(nums) + 1

while j < len(nums):
pres += nums[j]; j += 1
while pres >= s:
res = min(res, j - i)
pres -= nums[i]; i+= 1
return res if res != len(nums) + 1 else 0
``````

Code: O(nlogn) - search if a window of size k that satisfies the condition

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int i = 1, j = nums.length, min = 0;
while (i <= j) {
int mid = (i + j) / 2;
if (windowExist(mid, nums, s)) {
j = mid - 1;
min = mid;
} else i = mid + 1;
}
return min;
}

private boolean windowExist(int size, int[] nums, int s) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
if (i >= size) sum -= nums[i - size];
sum += nums[i];
if (sum >= s) return true;
}
return false;
}
}
``````

Python

``````class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
i,j, res = 1, len(nums), 0

def windowExists(size): # for a fixed window size "size": whether there is window sum >= s
acc = 0
for i in range(len(nums)):
acc += nums[i]
if i >= size: acc -= nums[i - size]
if acc >= s:
return True
return False

while i <= j:
mid = (j - i >> 1) + i
if windowExists(mid):
j = mid - 1
else:
i = mid + 1

return i if i <= len(nums) else 0
``````