Determining the total of each sub-array with a size of k in a given array by employing the sliding window technique

Question

Determining the total of each sub-array with a size of k in a given array by employing the sliding window technique

Is it possible to calculate the sum of all k-sized sub-arrays in an array using a sliding window algorithm? Is this approach valid, and if not, what are the reasons behind it?

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

Expected output should be 27

javascript arrays

Answer 1

Answer №1

Upon examining your code, I noticed that it implements the window sliding algorithm, albeit in a slightly different manner than what I am accustomed to. Personally, I would adjust the movement of the "window" by starting from the last visited index instead of going from the 0 index twice.

The main variation lies in how we handle moving "the tail" - while you add the value of 'k', I prefer to subtract it.

If I were to implement this, my approach would look like this:

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

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

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

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

Answer 2

Upon examining your code, I noticed that it implements the window sliding algorithm, albeit in a slightly different manner than what I am accustomed to. Personally, I would adjust the movement of the "window" by starting from the last visited index instead of going from the 0 index twice.

The main variation lies in how we handle moving "the tail" - while you add the value of 'k', I prefer to subtract it.

If I were to implement this, my approach would look like this:

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

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

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

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

Answer 3

Answer №2

When dealing with the array, keep reducing it until the index is less than the specified value k. Simply add the current number to both the total and subTotal. Then, calculate the new value for newSubTotal by adding the current number to the previous sum while removing the first number used in creating the initial subTotal. Finally, combine the newSubTotal with the total to obtain the updated total.

const findSumOfSubArrays = (arr, k) =>
  arr.reduce(([total, subTotal], n, i) => {
    if(i < k) return [total + n, subTotal + n];
    
    const newSubTotal = subTotal + n - arr[i - k];
    
    return [total + newSubTotal, newSubTotal]
  }, [0, 0])[0];

const inputArray = [1, 2, 3, 4, 5];
const windowSize = 3;

console.log(findSumOfSubArrays(inputArray, windowSize));

Answer 4

When dealing with the array, keep reducing it until the index is less than the specified value k. Simply add the current number to both the total and subTotal. Then, calculate the new value for newSubTotal by adding the current number to the previous sum while removing the first number used in creating the initial subTotal. Finally, combine the newSubTotal with the total to obtain the updated total.

const findSumOfSubArrays = (arr, k) =>
  arr.reduce(([total, subTotal], n, i) => {
    if(i < k) return [total + n, subTotal + n];
    
    const newSubTotal = subTotal + n - arr[i - k];
    
    return [total + newSubTotal, newSubTotal]
  }, [0, 0])[0];

const inputArray = [1, 2, 3, 4, 5];
const windowSize = 3;

console.log(findSumOfSubArrays(inputArray, windowSize));

Determining the total of each sub-array with a size of k in a given array by employing the sliding window technique

Answer №1

Answer №2

Similar questions

Is it feasible to utilize the draw_buffer extensions in THREE.js?

What is the best method to include numpy array or float values in an AWS API response?

JavaScript - Endless State Loop - Panning Operation

The array subscript cannot be of type `int[int]`

Adjusting Specific Time for Jquery to Change Date if Less Than X Value

Executing a C# function from an HTML hyperlink

Angular Material's input field is not correctly binding to localeString

Do not try to render objects as a React child. If you intended to display a group of children, make sure to use an array instead

lua update/swap 2D array

I could really use some assistance with this script I'm working on that involves using ($

Is it possible for search engines to crawl and index specific pages within a web application that is powered by

Submit a form to transfer information to a different page, authenticate the data, and finally submit it

Redis appears to be missing the expected results

Issue with three.js: animations not playing when changing characters

Locating the position of data within an array using PHP

Resolving the issue of "Mixed Active Content" CORS error detection

Is there a better method to organize an Array of Objects?

set a value to a global array within a function

The ajaxStart event does not seem to be triggering when clicked on

Utilizing Express middleware to serve routes in Sails.js