Minimum Size Subarray Sum

Given an array of positive integers, nums, and a positive integer, target, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray is found, return 0.

Given an array of positive integers, nums, and a positive integer, target, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray is found, return 0.

Minimum Size Subarray Sum

Constraints

• 1 ≤ target ≤ 10⁹
• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁴

Examples

Sample Example 1

Input:

• nums = [2, 3, 1, 2, 4, 3]
• target = 7

Output: 2

Explanation: The subarray [4, 3] has a sum of 7, which meets the target. Its length of 2 is the smallest among all valid subarrays.

Sample Example 2

Input:

• nums = [1, 4, 4]
• target = 4

Output: 1

Explanation: The subarray [4] alone already meets the target sum of 4, so the minimum length is 1.

Sample Example 3

Input:

• nums = [1, 1, 1, 1, 1, 1, 1, 1]
• target = 11

Output: 0

Explanation: The sum of the entire array is 8, which is less than the target of 11. So no valid subarray exists.

Solution

We go through the array while keeping a running sum. Whenever this sum becomes greater than or equal to the target, we save the current window's length (if it's the smallest one so far) and start shrinking the window from the left.

Steps

• We use two pointers: start and end. We move end forward, one step at a time, adding each number to our running sum.
• Every time sum becomes greater than or equal to target:
  • We calculate the size of the current window (end - start + 1) and check if it's smaller than the best one we've found so far.
  • We then shrink the window from the left: we subtract nums[start] from sum and move start forward by one.
  • We keep shrinking as long as sum is still greater than or equal to target.
• After going through the whole array, if we found at least one valid window, we return its length. If we never found one, we return 0.

Code

var minSubArrayLen = function (target, nums) {
    let windowSize = Infinity;
    let start = 0,
        sum = 0;

    for (let end = 0; end < nums.length; end++) {
        sum += nums[end];

        while (sum >= target) {
            let currSubArrSize = end + 1 - start;
            windowSize = Math.min(windowSize, currSubArrSize);
            sum -= nums[start];
            start += 1;
        }
    }

    if (windowSize != Infinity) {
        return windowSize;
    }
    return 0;
};