Minimum Size Subarray Sum

Leet code Link - https://leetcode.com/problems/minimum-size-subarray-sum/

Complexity - Medium

Description

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

Solution

We can use the sliding window algorithm and also calculating sum while iterating through the numbers

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum =0; int res =Integer.MAX_VALUE;
        int left = 0,right =0;
        while(right<nums.length){
            sum+=nums[right];

            while(sum>=target){
                res=Math.min(res,right-left+1);
                sum-=nums[left++];
            }
            right++;
        }
        return res==Integer.MAX_VALUE?0:res;
    }
}

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

Time Complexity - O(N) Space Complexity - O(1)