can't pass challenge if code not optimized further-CodePudding

I can't pass this coding challenge: Code Challenge: https://www.codewars.com/kata/550f22f4d758534c1100025a/train/javascript

because my code is TOO SLOW. I'm not sure which part of my code is causing the problem. That's why I need help to optimize it.

function dirReduc(arr){
  if (arr.length === 0 || arr.length === 1) return [];
  let lengthTracker = arr.length;
  for (let i = 0; i < arr.length; i  ) { 
  if (lengthTracker > arr.length) {
    lengthTracker = arr.length;
    i = 0;
  }
    switch(arr[i]) {
  case "NORTH":
 arr[i-1] === "SOUTH"? arr.splice(i-1,2) : 
 arr[i 1] === "SOUTH"? arr.splice(i,2) : null
  break;
  case "SOUTH":
 arr[i-1] === "NORTH"? arr.splice(i-1,2) : 
 arr[i 1] === "NORTH"? arr.splice(i,2) : null
    break;
  case "EAST":
 arr[i-1] === "WEST"? arr.splice(i-1,2) : 
 arr[i 1] === "WEST"? arr.splice(i,2) : null
    break;
  case "WEST":
 arr[i-1] === "EAST"? arr.splice(i-1,2) : 
 arr[i 1] === "EAST"? arr.splice(i,2) : null
    break;
}
i===arr.length-1? i=0:null
  }
 return arr;
}

CodePudding user response：

Splicing can be expensive. We can form a recurrence that assumes the function has already correctly reduced the next part of the list:

function matches(a, b){
  return (a == "NORTH" && b == "SOUTH") ||
    (b == "NORTH" && a == "SOUTH") ||
    (a == "EAST" && b == "WEST") ||
    (b == "EAST" && a == "WEST");
}


function f(A, i=0){
  if (i == A.length)
    return [];
    
  const rest = f(A, i   1);
  const [head,...tail] = rest;
  
  if (head){
    if (matches(A[i], head))
      return tail;
    else
      return [A[i]].concat(rest);
  }
  
  return [A[i]];
}

CodePudding user response：

I see several problems with this. First, as I mentioned in the comments, splicing long arrays is costly and makes your algorithm O(n^2). Simple and faster would be to use a read-point and a write-point to copy the elements into itself one cell at a time, just skipping over the annihilations and then use splice once at the end to trim the uncopied cells of the end of the array. This would make it O(n).

Secondly, your code is looking both forward and backward for matches which is both unnecessary and can be confusing. Finally, there's no need for a switch (...) as all of the branches do the same thing.

Here is how I would use your code to accomplish this, changing the things mentioned above and noted in the comments.

function dirReduc(arr){
    if (arr.length === 0 || arr.length === 1) return [];
    let lengthTracker = 0;                  // the write-point

    for(let i = 0; i < arr.length; i  ) {   // i is the read-point
        if(lengthTracker == 0) {
            // if no output, copy readpoint and advance write-point
            arr[lengthTracker] = arr[i];
            lengthTracker  ;
        } else {
            // replaces switch()
            if (((arr[lengthTracker-1] === "NORTH") && (arr[i] === "SOUTH"))
             || ((arr[lengthTracker-1] === "SOUTH") && (arr[i] === "NORTH"))
             || ((arr[lengthTracker-1] === "EAST") && (arr[i] === "WEST"))
             || ((arr[lengthTracker-1] === "WEST") && (arr[i] === "EAST"))) {
                lengthTracker--;    // annihilate by decrementing the writepoint
            } else {
                // copy readpoint to after writepoint and advance
                arr[lengthTracker  ] = arr[i];
            }
        }
    }
    //trim the array to only include what was written
    arr.splice(lengthTracker);
    return arr;
}