Max Length of Subarray with Given Sum Limit in JavaScript Array
Given an array, our task is to find the maximum length of a subarray whose sum does not exceed a given value. We can use different approaches like the Brute Force Approach and the Sliding Window Approach to find the maximum length of a subarray.
Below are the approaches to find the maximum length of a subarray with a sum not exceeding a given value:
Table of Content
- Using the Brute Force Approach
- Using Sliding Window Approach
Using the Brute Force Approach
In this approach, the code employs a brute force method to find the maximum length of a subarray in JavaScript. It iterates through each possible subarray, calculating the sum and updating the maximum length if the sum does not exceed a given value k. Finally, the method returns the maximum length of the subarray with a sum not exceeding k.
Example: The example uses the Brute Force method to find the maximum length with the sum not exceeding a given value.
function maxSubarrayLengthBruteForce(arr, k) {
let maxLength = 0;
for (let start = 0; start < arr.length; start++) {
let sum = 0;
for (let end = start; end < arr.length; end++) {
sum += arr[end];
if (sum <= k) {
maxLength = Math.max(maxLength, end - start + 1);
}
}
}
return maxLength;
}
const array1 = [1, 2, 3, 4, 5];
const k1 = 11;
console.log(maxSubarrayLengthBruteForce(array1, k1));
const array2 = [3, 1, 2, 1];
const k2 = 4;
console.log(maxSubarrayLengthBruteForce(array2, k2));
Output
4 3
Time Complexity: O(n^2)
Space Complexity: O(1)
Using the Sliding Window Approach
In this approach, the sliding window technique is used to find the maximum subarray length whose sum doesn’t exceed a given value k. It iterates through the array, adjusting the window boundaries to maintain the sum within k. Finally, it returns the maximum subarray length found.
Example: The example uses a sliding window technique to find the maximum subarray length with a sum not exceeding a given value.
function maxSubarrayLengthSlidingWindow(arr, k) {
let maxLength = 0;
let sum = 0;
let start = 0;
for (let end = 0; end < arr.length; end++) {
sum += arr[end];
while (sum > k) {
sum -= arr[start];
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
const array3 = [1, 2, 3, 4, 5];
const k3 = 11;
console.log(maxSubarrayLengthSlidingWindow(array3, k3));
const array4 = [3, 1, 2, 1];
const k4 = 4;
console.log(maxSubarrayLengthSlidingWindow(array4, k4));
Output
4 3
Time Complexity: O(n)
Space Complexity: O(1)