Maximum Sum Subarray of Size K, Applying Sliding Window pattern

Question: Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Eg: For given array A[] = {10,30,20,50,60,40,40} of size k = 2
The maximum sum subarray would be
sum = 50 + 60 = 100.

Brute Force: O(N*K) N = Size of Array.

Brute force solution would be to generate all possible subarray of size K and find the maximum among those subarrays.

var maxSubarray = function(arr,k){
  let max = 0;
  for(let i=0;i<arr.length-k+1;i++){
    let tempMax = 0;
    for(let j=i;j<i+k;j++){
      tempMax += arr[j];
    }
    if(tempMax > max){
      max = tempMax;
    }
  }
  return max;
};

Now let's think about optimizing it. Let's observe what are we actually doing at each step.

Let
A[] = [10,20,10,40,50,10,60]
K = 3

for index 0 : sum = 10 + 20 + 10 or index 0 + index 1 + index 2
for index 1 : sum = 20 + 10 + 40 or           index 1 + index 2 + index 3
for index 2 : sum = 10 + 40 + 50 or                     index 2 + index 3 + index 4
for index 3 : sum = 40 + 50 + 10 or                               index 3 + index 4 + index 5      

and so on..

From this, we can see that at each iteration, we sum up add the elements between index(i,i+k). But also observe that at each step we're repeating the same steps.

So as you can see we're repeating same steps, so now let's think about how can we avoid duplicate steps, this leads to our another observation that

for a given index i, sum = A[i] + A[i+1] + A[i+2] + ... + A[i+k];
for index i+1 sum = A[i+1] + A[i+2] + ... + A[i+k] + A[i+k+1];

so at each iteration i+1, we are subtracting A[i] and we're adding A[i+k+1].

And this, Ladies and Gentlemen is called a sliding window where at each step we add the next element and remove the previous element.

Let's code it !

var maxSubarray = function(arr,k){
  let max = 0;
  let windowSum = 0;
  let windowStart=0;
  for(let windowEnd=0;windowEnd<arr.length;windowEnd++){
      windowSum+=arr[windowEnd];
      if(windowEnd>=k-1){
        max = Math.max(windowSum,max);
        windowSum -= arr[windowStart];
        windowStart++;
      }
      console.log(windowSum,max);
  }
  return max;
};

That's it ! Now you know how to see the patterns and solve most commonly asked interview question. Your interview will be like :

Hope you understood and liked my explanation!

github:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/MaximumSubarraySum.js