Maximum Sum in a Sliding Window of Length w
Let’s talk about a Sliding Window problem and how to solve it.
The Sliding Window approach is useful when you have a set of data (like a string or array) and you are looking for a continuous subset of the data. We create a window (which can be a subarray or substring) and move the window depending on a condition.
Consider the following problem: Write a function which accepts an array of integers and a number called w. The function should calculate the maximum sum of w consecutive elements in the array.
Brute force solution — O(nw)
The brute force approach would be to use nested loops. We can already tell that this won’t be efficient, but it is still worthwhile to discuss.
The solution would be as follows:
First we check that the array is indeed longer than w. Otherwise we return null as we would not have enough integers in the array to add together.
Next we set a variable called maxSum to -Infinity which we will use to compare our sums in order to return the max at the end. We initialize maxSum to a small number so that any sums we compute as we iterate will be larger than it. We use -Infinity instead of 0 in case the array is filled with negative numbers.
We loop through the array from the first element until the last element that can start the sum. We don’t want to go to the last element in the array, rather the last element that still has w-1 elements after it that can be summed up.
For each iteration we run a loop from 0 to w (exclusive) in order to compute our sum.
We check if our sum is greater than the current maxSum and if so store it in the max variable.
And finally, after exiting the outer loop we return the maximum sum.
Sample code is provided below:
function maxSubarraySum(arr, w){ if (num > arr.length){
return null;
} let maxSum = -Infinity
for (let i = 0; i < arr.length - w + 1; i++){
let temp = 0;
for (let j = 0; j < w; j++){
temp += arr[i+j];
} if (temp > maxSum){
maxSum = temp;
}
}
return maxSum;
}
As we mentioned earlier this solution is inefficient because it uses nested loops. The time complexity of this solution is O(nw).
Sliding window solution — O(n)
We can come up with a more efficient solution using a sliding window.
The solution would be as follows:
Like last time we first check that the array is longer than w.
Then we create two variables, maxSum and tempSum.
We loop through the first w elements in the array, add them up, and store them in maxSum and tempSum.
Next we loop i through from w until the end of the array, sliding our window to the right. What this means is that instead of using an inner loop to compute the sum of the w elements starting from the current position, we use the sum we have already computed and update it to account for us moving one element to the right. This is done by subtracting the leftmost element (arr[i — w]) from the previous sum and adding the next element (arr[i]). Then we compare the new sum (tempSum) to our current maxSum and reassign maxSum if necessary.
Lastly, after exiting the loop, we return maxSum.
Sample code is provided below:
function maxSubarraySum(arr, w){ if (w > arr.length){
return null;
} let maxSum = 0;
let tempSum = 0; for (let i = 0; i < w; i++){
maxSum += arr[i]
} tempSum = maxSum; for (let i = w; i < arr.length; i++){
tempSum = tempSum - arr[i - w] + arr[i];
if (tempSum > maxSum){
maxSum = tempSum;
}
}
return maxSum;
}
As you can see this is a much more efficient solution as we completely eliminated the inner loop. The time complexity of this solution is O(n).
References:
Level Up Coding
Thanks for being a part of our community! Subscribe to our YouTube channel or join the Skilled.dev coding interview course.
