Description

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 <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Solution

This can be solved using sliding window operations. We start with two pointers left = right = 0. In this case, subarray is valid as long as the sum of all elements of subarray is less than or equal to target. We move the right pointer towards right as long as it is valid subarray. When it becomes invalid (sum of elements greater than target), we start incrementing left pointer until the array becomes valid again.

 1minimumLength = minimum possible value
 2left = right = 0
 3currentSum = 0
 4while right less than nums.length
 5    currentSum += nums[right]
 6    while currentSum >= target
 7        minimumLength = minimum of minimumLength and (right - left + 1)
 8        currentSum -= nums[left]
 9        left++  
10    right++
11    if minimumLength == minimum value 
12        return 0
13    else
14        return minimumLength

 1class Solution {
 2    public int minSubArrayLen(int s, int[] nums) {
 3        int minimumLength = Integer.MAX_VALUE;
 4        int left = 0, right = 0;
 5        int currentSum = 0;
 6        while (right < nums.length) {
 7            currentSum += nums[right];
 8            while (currentSum >= s) {
 9                minimumLength = Math.min(minimumLength, right - left + 1);
10                currentSum -= nums[left];
11                left++;
12            }
13            right++;
14        }
15        return minimumLength == Integer.MAX_VALUE ? 0 : minimumLength;
16    }
17}