Smallest Subarray with Sum#

Given an array consisting of n positive integers and a positive integer s, find the length of the smallest contiguous subarray with a sum ≥ s and return its length. If there is no such subarray satisfying the condition, return 0.

Example#

Solution#

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(s, nums) {
    if(!nums.length) return 0;
    var start=0, end=0;
    var sum = 0;
    var target = Infinity;
    while(start < nums.length){
        if( sum < s && end < nums.length){
            sum += nums[end++];
        }else{
            if(sum >= s && target > (end - start)) target = end - start;
            sum -= nums[start++];
        } 
    }
    return target === Infinity ? 0 : target;
};

Idea#

Using the two-pointer approach to form a dynamic sliding window. Where start is the initial pointer and end is the ending pointer, Infinity is a value representing infinity. The window is initially of size 0, and sum is initialized as 0. If sum < s, the end pointer keeps moving to the right as long as end is less than the length of nums. This is because the window values need to keep increasing to reach a sum ≥ s. When the sum of window values is greater than or equal to s, the start pointer moves to the right to reduce the size of the window. Reducing the window size continuously is necessary to obtain the length of the smallest contiguous subarray. When the end pointer reaches the end boundary of the nums array, it stops moving to the right and the start pointer continuously moves to the right until its length is equal to the length of the nums array. The loop ends, and finally, it is checked whether target is still equal to Infinity. If it is still equal to Infinity, no suitable subarray length is found, and 0 is returned; otherwise, target is returned.

Daily Challenge#

Question Source#