209. Minimum Size Subarray Sum

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.

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

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

1. Sliding Window - Time O(n), Space O(1)

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

2. Binary Search - Time O(nlog(n)), Space O(n)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l=0, h=nums.length;
        int res = 0;
        while(l <= h){
            int mid = l+(h-l)/2;
            if(isValid(mid,nums,target)){
                h = mid-1;
                res = mid;
            } else{
                l = mid+1;
            }
        }
        return res;
    }
    public boolean isValid(int size, int[] nums, int target){
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum+=nums[i];
            if(i >= size) sum-=nums[i-size];
            if(sum >= target) return true;
        }
        return false;
    }
}