LeetCode Java Solution — 209. Minimum Size Subarray Sum

We are given an array of positive integers called nums, and a positive integer called target. We need to find the smallest length of a subarray within “nums” whose sum is greater than or equal to “target”. If there is no subarray that meets the requirements, we return 0.

What is a subarray?

An array that is a part of another array, and the elements are neighboring each other.

Example:

myArray: [1, 3, 5, 8, 2, 4]

mySubarray: [3, 5, 8]

So, for this problem, let’s form an input array called “nums” and a target number called “target”. Then, we solve the output by finding the smallest length of a subarray from the array “nums” whose sum is greater than or equal to “target”.

Example:

target: 4

nums: [2, 4, 4]

Output: the smallest length would be 1

Notice that 1 is the output because after sifting through the elements, we can see that the subarray of [4] with a length of 1 is the smallest length whose sum is greater than or equal to the target number 4. Therefore, 1 would be the smallest length of the subarray.

Problem Outline

Next, let’s list a few steps we need to solve this problem:

Step 1) finding the size of the array

Step 2) figure out how to traverse array, two pointer method with loops

Step 3) figure out how to keep track of sum of numbers to find minimum subarray length and the min length each subarray

Step 4) note any constraints

Step 5) draw out the concept

Then, put it all together in a coding language!

Problem Outline Explained

Step 1) To find the size of the array, we can use the length attribute of the Array class:

nums.length

Step 2) To figure out how to traverse through each number in the array, we can use a variety of techniques. For this problem, we will go with a two pointer technique.

Step 3) Since we are going with a two pointer technique, we can keep track of the sum of the numbers and minimum length of the subarray in while loops, updating the variables while iterating through the array.

Step 4) Some constraints to consider are subarrays that are not found with the target number, so we can set a variable and say:

if (min_length == Integer.MAXVALUE)

  return 0;

Step 5) For the coding part, we want to address the constraint of an empty array and any variables and loops we will need. Also, while in the loop, we need to move the pointer and update variables in order to find the target sum and the minimum length of the subarray according to that sum. Finally, we return the minimum length of the subarray.

Code Explained

Header for method:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

Empty array constraint:

        if (nums.length == 0)
            return 0;

Declare two pointers, sum variable, and minimum length variable

        int i = 0;
        int j = 0;
        int sum = 0;
        int min_length = Integer.MAX_VALUE;

First while loop header with j pointer:

        while (j < nums.length){

Update sum variable for element at j index, j pointer moves up one index:

            sum = sum + nums[j++];

If sum is found to be greater than or equal to the target, enter another while loop and find the minimum value between min_length and the two pointers. Then, update the sum again and move i pointer up one index in array:

            while (sum >= target){
                min_length = Math.min(min_length, j - i);
                sum = sum - nums[i++];
            }
        }

Check if the min_length variable changed, return 0 if no change, return the min length variable if changed:

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

Full code:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0)
            return 0;

        int i = 0;
        int j = 0;
        int sum = 0;
        int min_length = Integer.MAX_VALUE;
        while (j < nums.length){
            sum = sum + nums[j++];

            while (sum >= target){
                min_length = Math.min(min_length, j - i);
                sum = sum - nums[i++];
            }
        }

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

Credit goes to the problem solver jeantimex on LeetCode and their solution. This discussion thread has more replies with good explanations for this problem.

Thanks for reading!