Improve the speed of a JavaScript function

Question

I have a task I found on CodeWars and I managed to solve it, however, after submitting is says:

Execution timed out: (12000 ms)

When I try to test the function is passed, but I guess it is too slow. Before you condemn me for not finding the answer on my own. I don't really care about submitting that as a response, but I have no idea how to make it faster and that is why I am here. Here is the function:

const ls = [0, 1, 3, 6, 10]

const partsSums = (ls) => {
    const sum = []
    for(let i = 0, len = ls.length; i < len + 1; i++) {
        let result = ls.slice(i).reduce( (accumulator, currentValue) => accumulator + currentValue, 0)
        sum.push(result)
    }
    return sum
}

Here are the instructions:

Let us consider this example (array written in general format):

ls = [0, 1, 3, 6, 10]

Its following parts:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

The corresponding sums are (put together in a list): [20, 20, 19, 16, 10, 0]

The function parts_sums (or its variants in other languages) will take as parameter a list ls and return a list of the sums of its parts as defined above.

Answer 1

For this kind of array maipulations, you better not use build in methods, like slice or reduce, because they are slow in comparison to a for loop, or any other looping approaches.

This approach takes a sinlge loop and uses the index for getting a value of the given array and takes the last sum of the new array.

Some speed tests on Codewars: Sums of Parts:

• 5621 ms with sparse array sum = []; sum[i] = 0; (the first version of this answer),
• 3452 ms with Array(i + 1).fill(0) and without sum[i] = 0;,
• 1261 ms with Array(i + 1) and sum[i] = 0; (find below),
• 3733 ms with Icepickle's first attempt.

const
    partsSums = (ls) => {
        let i = ls.length;
        const sum = Array(i + 1);

        sum[i] = 0;
        while (i--) sum[i] = sum[i + 1] + ls[i];

        return sum;
    },
    ls = [0, 1, 3, 6, 10];

console.log(...partsSums(ls));

Answer 2

You can still take a more functional approach but optimise the way you're doing the calculations.

Here is the idea - since you're trying to sum all items, then sum all but the first, then sum all but the second, etc., mathematically equivalent to getting the sum then subtracting from it each number in order and keeping the total.

[sum([41, 42, 43]), sum([42, 43]), sum([43]), sum([])]

is the same as:

total = sum([41, 42, 43])
[total - 0, total - 0 - 41, total - 0 - 41 - 42, total - 0 - 41 - 42- 43]

is the same as:

total = sum([41, 42, 43])
[total -= 0, total -= 41, total -= 42, total -= 43]

Generalised, this looks like:

total = sum([a1, a2, ..., aN])
[total -= 0, total -= a1, total -= a2, ..., total -= aN]

Using the trusty Array#reduce we can derive the sum once. Then we can derive the new array using Array.map using ls.map(num => total -= num).

The only problem here is that we get one less item - we don't calculate the initial total -= 0 which has to exist for all items. One way to do it is to append it to the start [0].concat(ls) will create the correct array to map over. However, since we already know what the value there would be, we can skip this step and directly substitute with total (after all the result of total -= 0 is total and leaves total unchanged). So, we can directly use [total].concat(ls.map(num => total -= num)) to start with total and add the rest of the items. to the end.

const ls = [0, 1, 3, 6, 10]

const partsSums = (ls) => {
    let total = ls.reduce((a, b) => a + b, 0);
    
    return [total]
      .concat(
        ls.map(num => total -= num)
      );
}

console.log(partsSums(ls));

Answer 3

Personally, I would just use the previous sum to calculate the next, I don't see any need to re-iterate all the previous sums, so, I would probably go for a basic loop and then reverse the results, like so

function partsSums(ls) {
  const result = [0];
  if (ls.length === 0) {
    return result;
  }
  for (let i = ls.length, q = 0; i--; q++) {
    result.push(result[q] + ls[i]);
  }
  return result.reverse();
}

or, without reversing, look more like Nina's solution (except for predefining the length of the array)

function partsSums(ls) {
  const len = ls.length;
  const result = new Array(len+1);
  result[len] = 0;
  for (let i = len; i--;) {
    result[i] = result[i+1] + ls[i];
  }  
  return result;
}

Both also seem to run faster than Nina's on codewars nodejs engine, in the first part probably because of push, in the second one, probably because the array's length is defined from the start, for more information see this question

Answer 4

A solution using normal for loop along the time of execution .

var arr = [0, 1, 3, 6, 10];


function giveList(array){
    
    var sum=0;
    for(let i=0;i<array.length;i++){
       sum=sum+array[i];
    }

    var result = [];
    result.push(sum);
    var temp;
    for(let i=0;i<array.length;i++){
       temp=sum-array[i];
       result.push(temp); 
       sum=sum-array[i];
        
     }
 return result;
}

console.time();
console.log(giveList(arr));
console.timeEnd();

Answer 5

const partsSums = (ls, sum = 0) =>
   [...ls, 0].reverse().map(x => sum = x + sum).reverse();

Takes around 1100 ms when I run it on CodeWars, which is slightly faster than other answers.

Answer 6

The repeated operation is too more. e.g: when you compute sum of [3, 6, 10], the up step [1, 3, 6, 10] already compute。 So you can think in another direction, back to end compute the sum of array

const ls = [0, 1, 3, 6, 10];

function partSums(ls) {
   const len = ls.length;
   const dp = [];

   if(len === 0) { return [0] }
   dp[len] = 0;
   dp[len - 1] = ls[len - 1];
   for (let i = len - 2; i >= 0; i--) {
     dp[i] = dp[i + 1] + ls[i];
   }

   return dp;
}