Reacto

MinSubarrayLength.md

Min Subarray Length

Prompt

Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer. This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.

Example

minSubArrayLen ([2,3,1,2,4,3], 7) -> 2
minSubArrayLen ([2,1,6,5,4], 9) -> 2
minSubArrayLen ([3,1,7,11,2,9,8,21,62,33,19], 52) ->1
minSubArrayLen ([1,4,16,22,5,7,8,9,10], 39) -> 3
minSubArrayLen ([1,4,16,22,5,7,8,9,10], 55) -> 5
minSubArrayLen ([4,3,3,8,1,2,3], 11) -> 2
minSubArrayLen ([1,4,16,22,5,7,8,9,10], 95) -> 0

Approach

The solution uses sliding window approach that two pointers keep track of the size of the subarray and check if the sum of the current subarray is grater or equal to the target integer. The two pointers start at the 0 index of the array. check if the current total is greater or equal to the target and if not, increment end pointer by 1 to add next number to the subarray. if the sum matches or greater than the target, update the min length of the subarray and increment the start pointer by 1 to remove the first element of the subarray.

What is the sliding window? >> https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7#:~:text=The%20Sliding%20Window%20algorithm%20is,capture%20different%20portions%20of%20it.

Solution

function minSubArrayLen(arr, int) {
  let total = 0;
  let start = 0;
  let end = 0;
  let length = Infinity;

  while (start < arr.length) {
    // if current window doesn't add up to the given sum then 
    // move the window to right
    if (total < int && end < arr.length) {
      total += arr[end];
      end++;
    } else if (total >= int) {
      // if current window adds up to at least the sum given then
      // we can shrink the window 
      length = Math.min(length, end - start);
      total -= arr[start];
      start++;
    } else {
      // current total less than required total but we reach the end, 
      // need this or else we'll be in an infinite loop 
      break;
    }
  }

  return length === Infinity ? 0 : length;
}

Time complexity: O(N), Space Complexity: O(1)

Credit

This prompt is from Colt Steele's Algorithms and Data Structure course on Udemy. Also found this on leetCode https://leetcode.com/problems/minimum-size-subarray-sum/