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

by

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

  • 1

    This feels like this would be better suited for codereview.stackexchange.com? What’s the issue you’re having with the code?

    – 




  • There is no issue, it works, but I want to know if what i wrote here is a sliding window algorithm and what is the time and space complexity of this code

    – 

  • You seem to ask whether the current approach is ‘valid’. What do you mean with that if the code does seem to work?

    – 

  • I mean is this code a sliding window algorithm?

    – 

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));

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));

Leave a Comment