Minimum Size Subarray Sum

Problem

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 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 <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Solution

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let sum = 0; // sum of window
    let min = Infinity; // min length of valid subarray
    let l = 0; // left of window
    let r = 0; // right of window

    for (; r < nums.length; r++) {
        sum += nums[r];
        while (sum >= target) {
            min = Math.min(min, r - l + 1);
            sum -= nums[l];
            l++;
        }
    }
    return min === Infinity ? 0 : min;
};

We will implement a sliding window solution. Let l and r be the boundaries of our window, and sum be sum(nums[l:r + 1]). We slide the right boundary r every iteration. However, we only side the left boundary l when sum >= target (ie. elements in window is valid subarray as per the problem definition). Every time we slide l, we update min if a smaller subarray is encountered.