Algorithm Practice: Find Averages of Subarrays

Problem: Given an array, find the average of all contiguous subarrays of size ‘K’ in it.

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

To find the average of all contiguous subarrays of size ‘5’ in the given array. To solve this lets write it out:

1. For the first 5 numbers (subarray from index 0-4), the average is:
   (1+3+2+6-1)/5 => 2.2
2. The average of next 5 numbers (subarray from index 1-5) is:
   (3+2+6-1+4)/5 => 2.8
3. For the next 5 numbers (subarray from index 2-6), the average is:
   (2+6-1+4+1)/5 => 2.4
   … and so on

The final output containing the averages of all contiguous subarrays of size 5:

Output: [2.2, 2.8, 2.4, 3.6, 2.8]

The brute-force way to calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by ‘5’ to find the average would look like:

function find_averages_of_subarrays(arr, K) {
  const result = [];
  for (let i = 0; i < arr.length - K + 1; i++) {
    let sum = 0.0;
    for (let j = i; j < i + K; j++) {
      sum += arr[j];
    }
    result.push(sum / K); 
  }
  return result;
}

const result = find_averages_of_subarrays(5, [1, 3, 2, 6, -1, 4, 1, 8, 2]);
console.log(`Averages of subarrays of size K: ${result}`);

Time complexity: Since for every element of the input array, we are calculating the sum of its next ‘K’ elements, the time complexity of the above algorithm will be O(N∗K) where ’N’ is the number of elements in the input array.

The solution is inefficient because for any two consecutive subarrays of size ‘5’, the overlapping part (which will contain four elements) will be evaluated twice. There are four overlapping elements between the first subarray (indexed from 0–4) and the second subarray (indexed from 1–5).

To solve this problem more efficiently we should visualize each contiguous subarray as a sliding window of ‘5’ elements. We do this by reusing the sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find the sum and, as a result, the algorithm complexity will reduce to O(N).

Here is the algorithm using the Sliding Window approach:

function find_averages_of_subarrays(K, arr) {
  const result = [];
  let windowSum = 0.0,
      windowStart = 0;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    windowSum += arr[windowEnd]; // add the next element
    if (windowEnd >= K - 1) {
      result.push(windowSum / K); 
      windowSum -= arr[windowStart]; 
      windowStart += 1; 
    }
  }
  return result;
}

const result = find_averages_of_subarrays(5, [1, 3, 2, 6, -1, 4, 1, 8, 2]);
console.log(`Averages of subarrays of size K: ${result}`);

Conclusion: The Sliding Window algorithm is very useful in saving time complexity when you need to calculate something among contiguous sublists of a given size (or varied size). Try using it in place of nested for loops and it will save you a lot of complexity!