Given I have an array of integers, I want to determine the shortest subarray length where the sum of all the values in the subarray are equal to or greater than the number provided
The array passed through will only ever contain integers (Positive and Negative whole numbers including 0).
The array passed through will never be empty.
The number passed through will always be positive(Greater than 0).
The number passed through might be longer than the array's length.
In the case where the number is larger than the array length, return 0.
minSubArrayLen([2,3,1,2,4,3], 7) // Return: 2 because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // Return: 2 because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // Return: 1 because 62 is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // Return: 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // Return: 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // Return: 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // Return: 0 because all the values added together do not equal 95In this algorithm, we will be using the sliding window method to evaluate subarrays of different lengths to find the smalled subarray required to equal or be greater than the targetSum.
Let's break down this example.
minSubArrayLen([2,3,1,2,4,3], 7);We have our array of integers ([2,3,1,2,4,3]) and the target sum (7).
First, we can define the window as being 1 value wide.
[2,3,1,2,4,3]
^
windowSum = 2;
targetSum = 7;
startIndex = 0;
endIndex = 0;
minSubarrayLength = 1;Since the windowSum is not greater than or equal to the target sum, we need to increase the window size.
To do this we can add 1 to the endIndex.
[2,3,1,2,4,3]
^-^
windowSum = 5;
targetSum = 7;
startIndex = 0;
endIndex = 1;
minSubarrayLength = 2;We now have the startIndex of the window at 0 and the endIndex of the window at 1, making this window 2 elements wide.
Because we've increased the size of the window, we also increased the minSubarrayLength to match the window size.
We will need to continue to increase the window size until the windowSum is greater than or equal to the targetSum.
[2,3,1,2,4,3]
^-^-^
windowSum = 6;
targetSum = 7;
startIndex = 0;
endIndex = 2;
minSubarrayLength = 3;[2,3,1,2,4,3]
^-^-^-^
windowSum = 8;
targetSum = 7;
startIndex = 0;
endIndex = 3;
minSubarrayLength = 4;Now that we have a windowSum that is greater than or equal to the targetSum, we need to see if we can decrease the minSubarrayLength.
To do this, we will need to remove the first element from the subarray and re-evaluate the windowSum.
In essance, shrinking the window by one element by moving the startIndex forwards by one and not touching the endIndex.
[2,3,1,2,4,3]
^-^-^
windowSum = 6;
targetSum = 7;
startIndex = 1;
endIndex = 3;
minSubarrayLength = 4;We shrank window and now the sum is less than the targetSum.
We must grow the window again until it is greater than or equal to the targetSum.
[2,3,1,2,4,3]
^-^-^-^
windowSum = 10;
targetSum = 7;
startIndex = 1;
endIndex = 4;
minSubarrayLength = 4;Then, we attempt to shrink the window again!
[2,3,1,2,4,3]
^-^-^
windowSum = 7;
targetSum = 7;
startIndex = 2;
endIndex = 4;
minSubarrayLength = 3;This time we were successfull in shrinking the window because 1 + 2 + 4 = targetSum.
We decreased the minSubarraylength since we now know there is a subarray of 3 integers that are equal or greater than the targetSum.
Let's attempt to decrease the subarray length some more.
[2,3,1,2,4,3]
^-^
windowSum = 6;
targetSum = 7;
startIndex = 3;
endIndex = 4;
minSubarrayLength = 3;The decrease in window size resulted in the windowSum being less than the targetSum.
Let's increase the window size again.
[2,3,1,2,4,3]
^-^-^
windowSum = 9;
targetSum = 7;
startIndex = 3;
endIndex = 5;
minSubarrayLength = 3;Finally, we can try one last time to decrease the minSubarraylength.
[2,3,1,2,4,3]
^-^
windowSum = 7;
targetSum = 7;
startIndex = 4;
endIndex = 5;
minSubarrayLength = 2;Success! The minSubarrayLength is 2.
We can start by defining our windowSum, startIndex, endIndex, and minSubarrayLength variables.
We want to set the minSubarrayLength equal to Infinity to make sure our min length is the most accurate.
+// Difine a variable to keep track of the window sum
+// Define a variable to act as the index of the start of the window
+// Define a variable to act as the index of the end of the window
+// Define a variable to act as the min subarray length to return at the end equal to InfinityNow let's define a while loop where the condition is if the startIndex is less than the arr.length.
This allows us to loop indefinitely until the startIndex of the window is at the end of the array.
Having a for loop here would be too restrictive since we need to grow and shink the window.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
+// Start a while loop with a condition that startIndex is less than arr.lengthNext, we want to check if the windowSum is less than the targetSum and if the endIndex of the window is not at the end of the array.
If these are both true, we should add the value at arr[endIndex] to windowSum and increase the window size again.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
// Start a while loop with a condition that startIndex is less than arr.length
+ // if windowSum is less than targetSum and endIndex is less than arr.length
+ // add the value at arr[endIndex] to windowSum
+ // endIndex++If the windowSum is greater than or equal to the targetSum, we should update the minSubarrayLength to be either the startIndex minus endIndex or the current minSubarraylength, whichever is the smallest.
We use the startIndex minus endIndex because the difference would represent the size of the current window.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
// Start a while loop with a condition that startIndex is less than arr.length
// if windowSum is less than targetSum and endIndex is less than arr.length
// add the value at arr[endIndex] to windowSum
// endIndex++
+ // else if windowSum is greater than or equal to targetSum
+ // set minSubarrayLength to either minSubarrayLength or startIndex minus endIndex, whichever is smallerWe need to attempt to shrink the window size now and to do this we will subtract the value at the start of the window and move the starIndex forwards by 1.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
// Start a while loop with a condition that startIndex is less than arr.length
// if windowSum is less than targetSum and endIndex is less than arr.length
// add the value at arr[endIndex] to windowSum
// endIndex++
// else if windowSum is greater than or equal to targetSum
// set minSubarrayLength to either minSubarrayLength or startIndex minus endIndex, whichever is smaller
+ // subtract the value at arr[startIndex] from windowSum
+ // startIndex++Now we have the logic to grow, shrink, and move the window.
If none of the logic before this was satisfied, that would mean we have reached the end of the array and we need to break the loop.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
// Start a while loop with a condition that startIndex is less than arr.length
// if windowSum is less than targetSum and endIndex is less than arr.length
// add the value at arr[endIndex] to windowSum
// endIndex++
// else if windowSum is greater than or equal to targetSum
// set minSubarrayLength to either minSubarrayLength or startIndex minus endIndex, whichever is smaller
// subtract the value at arr[startIndex] from windowSum
// startIndex++
+ // else, break the loopFinally, we will return minSubarrayLength and if it is equal to Infinity still, we return 0 because we have not touched the minSubarrayLength.
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
// Start a while loop with a condition that startIndex is less than arr.length
// if windowSum is less than targetSum and endIndex is less than arr.length
// add the value at arr[endIndex] to windowSum
// endIndex++
// else if windowSum is greater than or equal to targetSum
// set minSubarrayLength to either minSubarrayLength or startIndex minus endIndex, whichever is smaller
// subtract the value at arr[startIndex] from windowSum
// startIndex++
// else, break the loop
return minSubarrayLength === Infinity ? 0 : minSubarrayLength;Let's define our variables first.
function minSubArrayLen(arr, targetSum) {
// Difine a variable to keep track of the window sum
// Define a variable to act as the index of the start of the window
// Define a variable to act as the index of the end of the window
// Define a variable to act as the min subarray length to return at the end equal to Infinity
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
}Next, let's define the while loop.
function minSubArrayLen(arr, targetSum) {
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
// Start a while loop with a condition that start is less than arr.length
while (startIndex < arr.length) {}
}Then, let's check if the windowSum is less than the targetSum and if the endIndex of the window is not at the end of the array.
If these are both true, we should add the value at arr[endIndex] to windowSum and increase the window size again.
function minSubArrayLen(arr, targetSum) {
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
while (startIndex < arr.length) {
// if total is less than targetSum and end is less than arr.length
if (windowSum < targetSum && endIndex < arr.length) {
// add the value at arr[end] to total
// end++
windowSum += arr[endIndex];
endIndex++;
}
}
}Now let's add an else if statement to check if the windowSum is equal to or larger than the targetSum.
If it is, we need to update the minSubarrayLength and shrink the window by subtracting the value at arr[startIndex] and moving the startIndex forwards by one.
function minSubArrayLen(arr, targetSum) {
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
while (startIndex < arr.length) {
if (windowSum < targetSum && endIndex < arr.length) {
windowSum += arr[endIndex];
endIndex++;
} else if (windowSum >= targetSum) {
// else if total is greater than or equal to targetSum
// set minLength to either minLength or start minus end, whichever is smaller
minSubarrayLength = Math.min(minSubarrayLength, endIndex - startIndex);
// subtract the value at arr[start] from total
// start++
windowSum -= arr[startIndex];
startIndex++;
}
}
}Finally, let's break the loop if these conditions are not met and return minSubarrayLength since that would mean we reached the end of the array.
function minSubArrayLen(arr, targetSum) {
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
while (startIndex < arr.length) {
if (windowSum < targetSum && endIndex < arr.length) {
windowSum += arr[endIndex];
endIndex++;
} else if (windowSum >= targetSum) {
minSubarrayLength = Math.min(minSubarrayLength, endIndex - startIndex);
windowSum -= arr[startIndex];
startIndex++;
} else {
// else, break the loop
break;
}
}
return minSubarrayLength === Infinity ? 0 : minSubarrayLength;
}We now have an algorithm that will find the minimum subaray length to achieve a sum we provide.
Time Complexity - O(N)
Space Complexity - O(1)
function minSubArrayLen(arr, targetSum) {
let windowSum = 0;
let startIndex = 0;
let endIndex = 0;
let minSubarrayLength = Infinity;
while (startIndex < arr.length) {
if (windowSum < targetSum && endIndex < arr.length) {
windowSum += arr[endIndex];
endIndex++;
} else if (windowSum >= targetSum) {
minSubarrayLength = Math.min(minSubarrayLength, endIndex - startIndex);
windowSum -= arr[startIndex];
startIndex++;
} else {
break;
}
}
return minSubarrayLength === Infinity ? 0 : minSubarrayLength;
}