Question 250977 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Calculating the sum of all k-sized sub-arrays in an array using sliding window algorithm

I need to calculate the sum of all k-sized sub-arrays in an array using sliding window algorithm. Is that a valid sliding window algorithm? If not, why?

var sumOfSubArrays = function(arr, k) {
    let currentSubArray = 0;
    for(let i=0; i<k; i++) {
        currentSubArray += arr[i];
    }

    let sum = currentSubArray;

    for(let i=0; i<arr.length-k; i++) {
    sum += currentSubArray - arr[i] + arr[i+k];
    currentSubArray = currentSubArray - arr[i] + arr[i+k];
    }

    return sum;
};

let arr = [1,2,3,4,5]
let k = 3;

console.log(sumOfSubArrays(arr, k));

Should return 27

Tags:

2

Answers


  1. 0

    I analysed your code and it is actually window sliding algorithm, but done in a bit different way than I’m used to. I’d do it by moving the "window" a bit differently and not going from 0 index twice, but from the last visited index.

    Difference is on how we move "the tail" – I move it by subtracting "k" and you by adding it.

    My way of doing it would be this:

    // O(n) solution for finding sum of all k-sized sub-arrays of size k using window sliding algorithm
function sumOfSubArrays(arr, k) {
    let arrayLength = arr.length;
    let sum = 0;
    let finalSum = 0;
    // Find initial sum of first k elements
    for (let i = 0; i < k; i++) {
        sum += arr[i];
        finalSum = sum;
    }
    // Iterate the array once and increment the right edge
    for (let i = k; i < arrayLength; i++) {
        // Moving "window" to next element 
        sum += arr[i] - arr[i - k];

        // Add a sum of new sub-array to finalSum;
        finalSum += sum;
    }
    return finalSum;
}


let arr = [1, 2, 3, 4, 5]
let k = 3;

console.log(sumOfSubArrays(arr, k));
    Login or Signup to reply.
  2. 0

    Reduce the array, as long as the index is lesser than k just add the current number to the total, and subTotal. Afterwards calculate the newSubTotal by adding the current number to the last newSubTotal, and removing the 1st number used for creating the previous subTotal. Add the newSubTotal to the total to get the new total.

    const sumOfSubArrays = (arr, k) =>
  arr.reduce(([total, subTotal], n, i) => {
    // calculate the base total and subTotal
    if(i < k) return [total + n, subTotal + n];
    
    // sliding window
    const newSubTotal = subTotal + n - arr[i - k];
    
    return [total + newSubTotal, newSubTotal]
  }, [0, 0])[0];

const arr = [1, 2, 3, 4, 5]
const k = 3;

console.log(sumOfSubArrays(arr, k));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search