CODEWITHSUNDEEP
javascriptarraysloopsoptimization
skdfsdfa
skdfsdfa

Reputation: 77

Timeout/inefficiency error with "for" loop and array.reduce in Javascript

Working through a codewars challenge (Simple Fun #237: Suffix Sums), and while I'm passing all the tests it's giving me a time-out error. The challenge is to make a new array from a given one, where each index of the new array is the summation of that same index in the original to the end of the original array.

For an array 1, 2, 3, -6, the output should be 0, -1, -3, -6.

b[0]= 1 + 2 + 3 - 6 = 0  
b[1]=     2 + 3 - 6 = -1  
b[2]=         3 - 6 = -3  
b[3]=           - 6 = -6

My code is this

function suffixSums(a) {
 var res=[]
 for(i=0;i<a.length;i++){
  var newarray=a.slice([i])
   res.push(newarray.reduce(function(acc, val){ return acc + val },0))
  }
  return res
}

Any clue what's up? I'm just learning still obviously, optimization is a whole new world for me

Upvotes: 2

Views: 234

Answers (4)

Nina Scholz
Nina Scholz

Reputation: 386660

You could use the successor of an item and add the actual value while iterating from the end.

function suffixSums(a) {
    var i = a.length - 1;
    while (i--) {
        a[i] += a[i + 1];
    }
    return a;
}

console.log(suffixSums([1, 2, 3, -6]));

Upvotes: 1

Redu
Redu

Reputation: 26181

I would do this job like;

var arr = [1, 2, 3, -6],
    res = arr.reduceRight((r,n) => r[0] === void 0 ? [n] : [n+r[0]].concat(r),[]);
console.log(res);

Upvotes: 0

ibrahim mahrir
ibrahim mahrir

Reputation: 31712

You are wasting time because you calculate the sum of each items from scratch, you can start from the end of the array and accumulate the sum as you go:

function suffixSums(a) {
    var res = [],
        sum = 0;                              // sum of items from end to the current index (initialized with 0)
    for(var i = a.length - 1; i >= 0; i--) {  // loop from the end
       sum += a[i];                           // add the current number to sum
       res[i] = sum;                          // add the sum to the result array at index i (this line could be changed to: res.unshift(sum);)
    }
    return res;
}

console.log(suffixSums([1, 2, 3, -6]));

Upvotes: 0

James
James

Reputation: 22247

If you don't mind changing the original array (Codewars doesn't mind):

function suffixSums(a) {
 for(var i = a.length - 2; i > -1; i--)
   a[i] += a[i+1];
 return a;
}

Upvotes: 0

Related Questions