MinimumSizeSubarraySum.java

package two_pointers;

/**
 * Created by gouthamvidyapradhan on 03/12/2017.
 *
 * 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.

 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.

 click to show more practice.

 Credits:
 Special thanks to @Freezen for adding this problem and creating all test cases.

 Solution: O(n) solution. Solve using sliding window sub-array sum using two pointers.
 */
public class MinimumSizeSubarraySum {
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        int[] nums = {2,3,1,2,4,3};
        System.out.println(new MinimumSizeSubarraySum().minSubArrayLen(7, nums));
    }

    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0, count = 0, min = Integer.MAX_VALUE;
        for(int i = 0, j = 0; j < nums.length;){
            if(nums[j] >= s){
                return 1;
            } else{
                sum += nums[j];
                count ++;
                if(sum >= s){
                    min = Math.min(min, count);
                    while(j > i){
                        sum -= nums[i];
                        count --;
                        i ++;
                        if(sum < s) break;
                        min = Math.min(min, count);
                    }
                }
            }
            j ++;
        }
        if(min == Integer.MAX_VALUE){
            return 0;
        }
        return min;
    }
}