 # LeetCode Minimum Size Subarray Sum Solution

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.

Example 1:

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.

Example 2:

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

Example 3:

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

Constraints:

• `1 <= target <= 109`
• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 104`

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

## Solution

We want to use a sliding window to find the minimum subarray (window). Because the size of the window is unknown, we must use a flexible sliding window that searchs through all the valid windows that meet the requirement. We will apply the flexible sliding window template on this question. Our search starts on interval `(0,0)` and extends rightwards before the `total` reaches `target`. When the `total` succeeds the `target` we have found a valid subarray. Then, we start shrinking this subarray from the left finding a smaller subarray until the window is no longer valid. Afterwards, we continue this process until we iterate through the entire array to find the minimum size subarray that has sum >= `target`.

#### Implementation

``````1def minSubArrayLen(self, target: int, nums: List[int]) -> int:
2    size = len(nums)+1
3    total, l = 0, 0
4    for r in range(len(nums)):
5        total += nums[r]
6        while total >= target:       # valid
7            size = min(size, r-l+1)
8            total -= nums[l]
9            l += 1
10    return size if size != len(nums)+1 else 0``````

The above solution using a flexible sliding window uses `O(n)` time complexity. As a follow up, is there an algorithm that solves this question in `O(n log(n))`? Yes! Consider using the `n` elements in `nums` as a starting point of a subarray, and then use `O(log(n))` time complexity to find the endpoint of that subarray. This is can be done via a for loop and a binary search on a prefix sum array.

``````1def minSubArrayLen(self, target: int, nums: List[int]) -> int:
2    prefix_sum = 
3    for n in nums:
4        prefix_sum.append(prefix_sum[-1] + n)
5
6    size = len(nums)+1
7    for start in range(len(nums)):
8        total = 0
9        l, r, end = 0, len(nums)-1, -1
10        while l <= r:
11            mid = (l+r)//2
12            if prefix_sum[mid+1] - prefix_sum[start] >= target:
13                end, r = mid, mid - 1
14            else: l = mid + 1
15        if end != -1: size = min(size, end-start+1)
16    return size if size != len(nums)+1 else 0``````