Problem

Minimum Size Subarray Sum

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.

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.

Solution

We use 2 pointers for left and right end of the subarray. Increasing right pointer will increase sum, and increasing left pointer will decrease sum. We start at index 0 for both left and right pointer. Then we increase right. As soon as we get a subarray that is bigger than s, we decrease the sum by increasing left until the subarray no longer qualify. Then we increase right to make it qualify again, then we shrink the size until it is no longer qualify. That way, we find the answer in O(N) time with O(1) space cost. The left pointer and right pointer never across, so we have scanned all the possible subarrays with sum bigger than s.

public class MinSizeSubArraySum {
  public static int minSize(int[] a,int s) {//7
    //2,3,1,2,4,3
    //          .
    int N = a.length; //6
    int minSize = Integer.MAX_VALUE;
    int lo = 0;//4
    int sum = 0;
    for(int i = 0; i < N; i++) { //5
      sum += a[i];  //3
      while(sum >= s) {
        minSize = Math.min(minSize, i - lo + 1);//2
        sum = sum - a[lo++]; //3
      }
    }
    return (minSize == Integer.MAX_VALUE) ? 0 : minSize;
  }
  public static void main(String[] args) {
    System.out.println(minSize(new int[]{2,3,1,2,4,3}, 7));
    System.out.println(minSize(new int[]{1,1,1,2}, 7));
  }
}

Time complexity O(N), space complexity O(1).