CODEWITHSUNDEEP
javascript
Exitos
Exitos

Reputation: 29750

How do I optimise this javascript function for speed?

I just took the Codility tape equilibrium test here

As you can see from my score I didn't get good enough on how fast the function executes. Can anybody give me some pointers so I can optimise this code and get closer to 100%?

Here is the code...

function solution(A) {

    var minimumAbsDiff = null;

    for(var currentIndex =1;currentIndex < A.length;currentIndex ++){
        var bottomHalf = getTotal(0,currentIndex-1,A);
        var topHalf = getTotal(currentIndex,A.length-1,A);

         var absDiff = Math.abs(bottomHalf - topHalf);
         if(minimumAbsDiff == null){
            minimumAbsDiff = absDiff;
         }else{
            if(absDiff < minimumAbsDiff) minimumAbsDiff = absDiff;
         } 
    }

    return minimumAbsDiff;
}

function getTotal(start,end,arrayTocheck){
    var total = 0;
    for(var currentIndex = start;currentIndex <= end;currentIndex++){
        total = total + arrayTocheck[currentIndex];
    }
    return total;
}

Upvotes: 1

Views: 172

Answers (1)

Bergi
Bergi

Reputation: 665456

You don't want to optimise speed. You want to lower the algorithmic complexity. Your current algorithm is O(n²), while the taks description explicitly stated that

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

So what's the insight to make that possible? Each total difference is only a small distance from the others for P. If you compare the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])| for P and P+1, there is only a constant amount of work difference to be done.

function solution(A) {
     var left = 0,
         right = A.reduce(function(a, b) { return a + b; }, 0);
     var min = Infinity;
     for (var p = 0; p<A.length-1; p++) {
         left += A[p];
         right -= A[p];
         min = Math.min(min, Math.abs(left - right));
     }
     return min;
}

Upvotes: 4

Related Questions