21. Minimum Size Subarray Sum

Topic :

arrays

Difficulty :

medium

Problem Link :

problem statement

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

TIME COMPLEXITY : O(N)

SPACE COMPLEXITY : O(1)

import java.io.*;
import java.util.*;
class Minimum_Size_SubArray_Sum
{
  public static void main(String args[])
  {
     int target = 7;
     int[] nums = {2,3,1,2,4,3};
     System.out.println(minSubArrayLen(target,nums));
  }
  static int minSubArrayLen(int target, int[] nums) {
        int sum=0; // stores currSum
        int left=0; int right=0; // left and right to mark the window
        int minLen=Integer.MAX_VALUE;
        
        while(right<nums.length)
        {
            sum+=nums[right]; // add nums[right] to sum
            
            if(sum>=target) // if our sum target then it is a valid window
            {// we have to see if we can shrink this window
                while(sum>=target)// while the window is valid we shrink it
                {
                    sum-=nums[left]; // substract the nums[left] from sum to sum of curr shrinked window
                    left++;// increment the left pointer
                }
             // Note : when we come out of the loop the window is not a valid one
             // now sum<target
             // hence the last time the window was valid when our curr left pointer was at left-1
             // hence the valid window length = right-(left-1) + 1 => right-left+2   
               minLen=Math.min(minLen,right-left+2); 
            }
           
            right++; // increment the right pointer 
        }
        return minLen==Integer.MAX_VALUE? 0 : minLen ;
    }
}