Sliding Window - Minimum Size Subarray Sum

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.

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.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 1

Constraints:

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Solution 1 - Using sliding window technique, keep track of minimum window size where the sum of elements are greater than or equal to target

In this approach, we are going to apply sliding window technique using two pointers left and right, keep track of minimum window size when the sum of elements in that window is greater than or equal to the target.

Implementation steps:

First, create four variables left, right that we will use to adjust the window, sum to store sum of elements in current window, and min to hold the answer,initialize min with input arrray length +1, as the minimum will be less than the array size.
Next, run a while loop until right pointer reaches end of input array nums, and do the following:
- Take the current element from nums, and add it to the sum.
- Next, check if we are going out of bounds, that is check if the sum is greater than or equal to target, then capture the window size and store it in min, if it is less than any of the previous min that was found.
- Also, move the left pointer, and subtract the value at left pointer from sum since we are moving the sliding window.
- At the end of while loop increment right pointer to move to the next element in input array nums.
Finally, check if there is any minimum value found, i.e. check if min is still has the initialized value (nums.length +1), if it is then return '0', otherwise return min.

public class MinimumSizeSubArraySum { static int minSubArrayLen(int target, int[] nums) { int left = 0; int right = 0; int sum =0; int min = nums.length + 1; while(right < nums.length) { sum += nums[right]; while(sum >=target) { min = Math.min(right - left +1 , min); sum-=nums[left]; left++; } right++; } return min == nums.length +1 ? 0 : min; } public static void main(String[] args) { System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3})); System.out.println(minSubArrayLen(11, new int[]{1,1,1,1,1,1,1,1})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: