LeetCode 209 Minimum Size Subarray Sum (Java)

Problem : Medium

LeetCode: 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.

Thought

To solve this problem, first of all is to understand the given constraint:

  • All the integers in nums are positive.
  • Return a contiguous subarray.
  • Whenever it’s about looking for a contiguous subarray with all non negtive arrays, sliding window method should flag up.
  • Sliding window is a special two pointers methods.
  • I found a youtube video is particularly useful with great explanation and useful whiteboarding graphs: TECH DOSE
  • This is my first time trying to implement sliding window method. It’s fun!!!

    Steps:

    -Update soon

Solution: Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0;
        int shortest = Integer.MAX_VALUE; //set min to the max value then reduce it
        while(right< nums.length){
            sum += nums[right]; //add current element to sum by moving right pointer

            if(sum>= target){
                //check if current sum >= target
                // move left pointer to squeeze the window until sum < target (to find the first shortest window)
                while (sum >= target){
                    sum -= nums[left];
                    left ++;
                }
                //Below updated window would be (right -left +1) + 1 (the one before )
                shortest = Math.min(shortest, right-left+2);
            }
            right ++;
        }
        return shortest == Integer.MAX_VALUE ? 0: shortest;
       
    }
}

For more instructions head over to the LeetCode.

Written on September 22, 2022