## Given problem

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a contiguous subarray `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to `target`. If there is no such subarray, return 0 instead.

For example:

• 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] <= 105`

## Using brute-force solution

In this case, we need to iterate all contiguous subarrays in the `nums` array. So below is some steps to iterate all of them.

• Use two loops.

• The outer loop will be used to mark the beginning of the current subarray.
• The inner loop will be used to iterate all elements from that index of the outer loop.

• Calculate sum
• Then, compare sum with `target`’s value.

So, we have brute-force solution for this problem.

``````class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minSize = Integer.MAX_VALUE;
int outerIdx = -1;
int innerIdx = -1;

for (outerIdx = 0; outerIdx < nums.length; ++outerIdx) {
int sum = 0;
for (innerIdx = outerIdx; innerIdx < nums.length; ++innerIdx) {
sum += nums[innerIdx];

if (sum >= target) {
minSize = Math.min(minSize, innerIdx - outerIdx + 1);
break;
}
}
}

if (minSize == Integer.MAX_VALUE) {
return 0;
}

return minSize;
}
}
``````

The complexity of this solution:

• Time complexity: O(n^2)
• Space complexity: O(1)

## Using Binary Search algorithm with Prefix-sum

``````class Solution {
public int minSubArrayLen(int target, int[] nums) {
int size = nums.length;
if (size == 0) {
return 0;
}

int[] sums = new int[size + 1];
Arrays.fill(sums, 0);

for (int i = 1; i <= size; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}

System.out.println("Sums: " + Arrays.toString(sums));
int minSubArraySize = Integer.MAX_VALUE;

for (int i = 1; i <= size; ++i) {
int value = target + sums[i - 1];
int idx = lowerBound(sums, value);
if (idx != -1) {
minSubArraySize = Math.min(minSubArraySize, idx - i + 1);
}
}

return (minSubArraySize != Integer.MAX_VALUE) ? minSubArraySize : 0;
}

private static int lowerBound(int[] prefixSum, int target) {
int low = -1;
int high = prefixSum.length;

while (low + 1 != high) {
int mid = low + (high - low) / 2;

if (prefixSum[mid] < target) {
low = mid;
} else {
high = mid;
}
}

if (high < prefixSum.length) {
return high;
}

return -1;
}
}
``````

The complexity of this solution:

• Time complexity: O(nlogn)
• Space complexity: O(n)

## Wrapping up

Refer:

209. Minimum Size Subarray Sum