Minimum Size Subarray Sum | Sliding Window

Minimum Size Subarray Sum | Sliding Window

Find the minimum size subarray with sum greater than or equal to the target. 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 the 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

Approach:

Subarrays are arrays within another array. Subarrays contain a contiguous set of elements.

Consider an array {1,2,3,4}

List of all its subarrays are {},{1},{2},{3},{4},{1,2},{2,3},{3,4},{1,2,3,4}

We have to find a minimum size sub-array with a sum greater than or equal to the target. One approach would be to generate all the sub-arrays and find the subarray with minimal size and sum >= target. Of course, this is a very inefficient approach. So instead of that, we will use Sliding Window Approach.

Sliding Window is a window that moves through the array. Elements within that window are considered as a subarray. We calculate the sum of elements inside the array and check if it is greater than or equal to the target. The sliding window moves from left to right.  At each step 1 element go out and 1 element goes inside the window.

Slide Explanation:

Screenshot (14)
Screenshot (15)
Screenshot (16)
Screenshot (17)
Screenshot (19)
Screenshot (18)
previous arrow
next arrow

Algorithm:

  • Initially, the size of the sliding window is 1.
  • Keep adding elements inside the window until we get the sum >= target
  • When the target is reached, calculate window size and check if it is the minimum size.
  • Now Keep removing elements until the sum < target.

Program:

 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int size = nums.length;
        int sum = 0,start = 0;
        boolean reachedTarget = false;
        for(int end = 0; end<nums.length; end++)
        {
            //increase windowsize
            sum += nums[end];
            if(sum >= target)
            {
                reachedTarget = true;
                size = Math.min(size, end-start+1);
            }
                
            //shrink till we get sum lesser than target
            while(sum >= target )
            {
                //while decreasing also update minSize
                size = Math.min(size, end-start+1);
                sum -= nums[start];
                start++;
            }
            
        }
        return reachedTarget ? size : 0;  //sum not reached the target.
    }
}

 

Complexity

Time Complexity – O(n) since we traverse the input array only once

Space Complexity – O(1) since we are not using any extra space

 

You Might Also Like…

To find maximum of the numbers under Sliding Window

Check if single swap can make strings equal

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x