What is wrong with my Tape-Equilibrium solutions performance for Codility

Question

Here is my solution that doesn't pass the performance requirements. As far as I can tell it is similar to other solutions I have looked up:

function solution(A) {
    let slice = A.slice(1,A.length);
    let firstSliceSum = A[0];
    let lastSliceSum = slice.reduce((a, b) => a + b);
    let smallestValue = Math.abs(firstSliceSum-lastSliceSum);
    for(let i=1;i<A.length-1;i++){
        let shift = slice.shift();
        firstSliceSum=firstSliceSum+shift;
        lastSliceSum=lastSliceSum-shift;
        let diff = Math.abs(firstSliceSum-lastSliceSum);
        if(diff<smallestValue)smallestValue=diff;
    }
    return smallestValue;
}

It just has one for loop that iterates the elements, not counting the initial "reduce" function. I have seen similar Java solutions that are supposed to pass with 100%. Link to the challenge : https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

Are you able to specify what the performance requirements are? — Chris HG, Feb 05 '20 at 14:19
Not a javascript expert, but shift() seems to have O(n) complexity, so maybe worth replacing this with `let shift = A[i];`. — SaiBot, Feb 05 '20 at 14:25

score 1 · Accepted Answer · answered Feb 05 '20 at 15:05

A couple of issues here.

As pointed out, you are using shift() inside a loop which has a time complexity of O(n). ultimately making your code O(n²).
Second, you are considering the first index 0 sum as well whereas the constraints mentioned say for any 0 < P < N.

Quoting from the problem statement mentioned there:

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

So you will have to calculate from 1 till A.length-1.

Snippet:

function solution(A) {
  let slice = A.slice(1, A.length);
  let firstSliceSum = A[0];
  let lastSliceSum = slice.reduce((a, b) => a + b);
  let smallestValue = -1;
  for (let i = 1; i < A.length; i++) {
    let diff = Math.abs(firstSliceSum - lastSliceSum);
    if (smallestValue == -1 || diff < smallestValue) smallestValue = diff;
    firstSliceSum += A[i];
    lastSliceSum -= A[i];
  }
  return smallestValue;
}

console.log(solution([3, 1, 2, 4, 3]));

In the above(correct code), we initialize the smallestValue to -1 as absolute value can't go negative.
In the loop, we avoid .shift() and just take the differences of firstSliceSum and lastSliceSum.
Later, we reduce A[i] from lastSliceSum and add it to firstSliceSum as we need to consider A[i] for next upcoming split and remove it from right part of the split.

Thank you this is really thorough answer and explains everything! — somerandomusername, Feb 06 '20 at 10:16

What is wrong with my Tape-Equilibrium solutions performance for Codility

1 Answers1