Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum greater than equal to k. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7

the subarray [4,3] has the minimal length under the problem constraint

The problem is very similar to subarray with sum of kbut with a small difference, in this case we have to find an array of minimum size.

The problem can be solved by maintaining 2 pointers, very similar to minimum window substring. start,endpointers will be used to manage the size of window with sum k. The algo is as follows:

  • Increment the start index and sum elements along the path, continue adding up elements as long it is not greater than k
  • Once the sum is greater than or equal to k. Start incrementing the end index and decrease the value arr[end] from sum.
  • If the sum is less than k, that is the window size. Check if the size(start-end) is minimum, continue above step until end of array is reached

public class Solution { 
	int minSubArrayLen(int s, int[] nums) {
    int n = nums.length();
    int ans = INT_MAX;
    int end = 0;
    int sum = 0;
    for (int start = 0; start < n; start++) {
        sum += nums[i];
        while (sum >= s) {
            ans = min(ans, start + 1 - end);
            sum -= nums[end++];
        }
    }
    return (ans != INT_MAX) ? ans : 0;
 }
}