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;
}
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 off 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 to write-point and advance
arr[lengthTracker++] = arr[i];
} 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 writepoint and advance
arr[lengthTracker++] = arr[i];
}
}
}
//trim the array to only include what was written
arr.splice(lengthTracker);
return arr;
}
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]];
}