educative.io

Educative

Single loop "inchworm" (variable sliding window)

The solution can be found with a single loop. Asymptotically same as example solution.
Algorithm is variously called “caterpillar”, “inchworm” or variable sliding window.

    /**
     * Find smallest contiguous subarray length whose sum is *greater than or equal* to ‘S’.
     * time: O(n), space: O(1)
     * @default 0
     * @param s - Number - the desired minimum sum
     * @param arr - Array - array of positive Number
     **/
    const smallest_subarray_with_given_sum = function(s, arr) {
      if(s === 0) return 0;
      const n = arr.length;
      // this is caterpillar pattern - head moves forward, tail follows
      let minLen = Infinity;
      let head = 0;
      let tail = 0;
      let currLen = 0;
      let currSum = arr[0];
      while(tail < n && head < n) {
        currLen = head - tail + 1;
        if(currSum >= s) minLen = Math.min(currLen, minLen);
        if(minLen === 1) return minLen;  // base: 1 element equal sum, return 1
        if(currSum > s || currLen > minLen) { // pull up rear
          currSum -= arr[tail];
          tail += 1;
          continue;
        }
        head += 1;
        currSum += arr[head];
      }
    
      return minLen;
    };