# Minimum Size Subarray Sum

Given an array ofnpositive integers and a positive integers, 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.
``````

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

## Analysis

#### Two Pointers

• Time complexity: O(n)

Each element can be visited atmost twice, once by the right pointer(`j`) and (atmost)once by the left pointer (`i`).

• Space complexity: O(1)

##### Longest Substring Without Repeating Characters

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59103/Two-AC-solutions-in-Java-with-time-complexity-of-N-and-NLogN-with-explanation

@ lx223: As to NLogN solution, logN immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.

Time: O(nlogn) - outer loop O(n), binary search in each loop O(logn), thus O(n * logn)

Space O(n) - additional prefix sum array O(n)

## Solution

Two Pointers - Time: O(n), Space O(1)

@lacfo: It seems like that two while loops give O(N^2). But actually, for every j, i is not starting from 0. Pointer i will not go back, so in the worst case, pointer j moves forward n times and pointer i also moves forward n times.

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

Binary Search - Time: O(nlogn), Space O(n)

``````class Solution {
public int minSubArrayLen(int s, int[] nums) {
int[] sums = new int[nums.length + 1];
for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < sums.length; i++) {
int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
if (end == sums.length) break;
if (end - i < minLen) minLen = end - i;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

private int binarySearch(int lo, int hi, int key, int[] sums) {
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sums[mid] >= key){
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
}
}
``````

## Reference

https://leetcode.com/problems/minimum-size-subarray-sum/solution/

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59110/O\(N\)-template-for-Minimum-Size-Subarray-Sum-and-Minimum-Window-Substring-and-Longest-Substring-Without-Repeating-Characters

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59103/Two-AC-solutions-in-Java-with-time-complexity-of-N-and-NLogN-with-explanation