209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a

subarray whose 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] <= 104

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)).

Solution:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // mininal windown  (>= target )
        int left = 0;
        int right = 0;
        int minLength = Integer.MAX_VALUE;
        int n = nums.length;

        int cur = 0; // curWindow sum

        while(right < n){
            int curRight = nums[right];
            cur = cur + curRight;

            while(cur >= target){
                minLength = Math.min(minLength, right - left + 1);
                cur = cur - nums[left];
                left++;
            }

            right++;
        }

        // TC: O(2n)

        if (minLength == Integer.MAX_VALUE){
            return 0;
        }else{
            return minLength;
        }
    }
}

// TC: O(n)
// SC: O(1)

function minSubArrayLen(target: number, nums: number[]): number {
    // Goal: find the minimum length of a contiguous subarray
    // where the sum is greater than or equal to the target

    let left = 0;
    let right = 0;
    let minLength = Number.MAX_SAFE_INTEGER;
    let cur = 0;

    while(right < nums.length){
        cur = cur + nums[right];

        while(cur >= target){
            minLength = Math.min(minLength, right - left + 1);
            cur = cur - nums[left];
            left++;
        }
        right++;
    }

    return minLength === Number.MAX_SAFE_INTEGER ? 0 : minLength;
};

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;

        int left = 0;
        int curSum = 0;


        for (int right = 0; right < nums.length; right++){
            curSum = curSum + nums[right];

            while(curSum >= target){
                result = Math.min(result, right - left + 1);
                curSum = curSum - nums[left];
                left++;
            }

        }

        if (result == Integer.MAX_VALUE){
            return 0;
        }else{
            return result;
        }

    }
}

// TC: O(n)
// SC: O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;

        int left = 0;
        int curSum = 0;


        for (int right = 0; right < nums.length; right++){
            curSum = curSum + nums[right];

            while(curSum - nums[left] >= target){
                curSum = curSum - nums[left];
                left++;
            }

            if (curSum >= target){
                result = Math.min(result, right - left + 1);
                // suppose right == left  -> 1 -> +1
            }

        }

        if (result == Integer.MAX_VALUE){
            return 0;
        }else{
            return result;
        }

    }
}

// TC: O(n)
// SC: O(1)