Refactor Javascript to Optimize for Speed

Question

I was able to figure out a working solution to the problem but I would like to know how I could go about refactoring this code to make it faster. Thank you.

/*
    Given a sequence of integers as an array, determine whether it is     
    possible to obtain a strictly increasing sequence by removing no more 
    than one element from the array.
    */

//var array2 = [0, -2, 5, 6]; // expect true
//var array2 = [1, 1, 1, 2, 3]; // expect false
var array2 = [1, 2, 5, 5, 5] // expect false

function almostIncreasingSequence(sequence) {
  let passing = false;
  sequence.forEach((number, idx, array) => {
    let sequence2 = sequence.filter((num, id) => id !== idx);

    let answer = sequence2.every((num, idx, array) => {
      return idx === sequence2.length - 1 || num < sequence2[idx + 1];
    });

    if (answer) {
      passing = true;
    }

  });
  return passing;
}

console.log(almostIncreasingSequence(array2));

Answer 1

Note that we have a conflict when a[i] <= a[i - 1] as we want a strictly increasing sequence. There are two ways to solve the conflict. One is to remove a[i] from the array, hoping that a[i + 1] won't conflict with a[i - 1]. Another is to remove a[i - 1], hoping that a[i - 2] won't conflict with a[i].

As we have the case that a[i] <= a[i - 1], it should be better to remove a[i - 1] so that our new max element in the sequence is less or equal than before, thus giving more chances to have no conflict on next element. So if we can choose between removing a[i] and a[i - 1], removing a[i - 1] would be better.

We can remove a[i - 1] when a[i - 2] does not conflict with a[i]. In the code, sequence[prev - 1] is this a[i - 2], so in the case where there is a conflict, our only choice left is removing a[i].

To avoid actually removing elements on the array, I used the little trick of just doing a continue, which makes i increase but prev stays the same, thus making the new a[i] compare against a[i - 2] as they should be now next to each other in the strictly increasing sequence.

When we don't fall into the continue, we do prev = i instead of prev += 1 because we would actually need to add 2 to prev after we got into the continue and there was no conflict between a[i] and a[i - 2]. If we added just 1 to prev, we would have prev pointing to a[i - 1], but we can't have that as its the element we "removed" from the sequence.

function isAlmostIncreasingSequence(sequence) {
  var prev = 0;
  var removed = false;
  
  for (var i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[prev]) {
      if (removed == false) {
        removed = true;
        if (prev > 0 && sequence[i] <= sequence[prev - 1]) { // need to remove sequence[i] instead of sequence[prev]
          continue;           
        }
      } else {
        return false;
      }
    }
    prev = i;
  }
  
  return true;
}

var tests = [[0, -2, 5, 6], [1, 1, 1, 2, 3], [1, 2, 5, 5, 5], [1, 3, 2], [0, -2, 5, 6], [1, 2, 3, 4, 5, 3, 5, 6], [1, 1], [1, 2, 5, 3, 5], [1, 2, 3, 4, 3, 6]];

tests.forEach(function(arr){
  console.log(arr.join(","), isAlmostIncreasingSequence(arr));
});

Answer 2

If I'm understanding the problem right, you only need to make 1 pass through the sequence. You're looking for arrays where the difference between index (i-1) and (i) decreases only one time in the whole array.

(this code has gone through several edits to handle edge cases)

function almostIncreasingSequence(sequence) {
    if(sequence.length == 1)
        return true;

    var countDecreases = 0;
    var i = -1;
    for(var index=1; index<sequence.length; index++)
    {
        if(sequence[index-1] > sequence[index])
        {
            countDecreases++;
            i = index;
            if(countDecreases > 1)
                return false;
        }
    }
    var canRemovePreviousElement = (i == 1 || sequence[i-2] <= sequence[i]);
    var cannotRemoveSelectedElement = (i+1 < sequence.length && sequence[i-1] > sequence[i+1]);

    if(canRemovePreviousElement)
        return cannotRemoveSelectedElement;

    return (countDecreases == 1 && !cannotRemoveSelectedElement);
}

// Testing /////////////////////////////////

var passTestCases = {
    "remove index 0": [2, 0, 1, 2],
    "remove index 1": [0, 1, 0, 0, 1],
    "remove index (last-1)": [0, 1, -1, 2],
    "remove index (last)": [0, 1, 2, -1],
    "remove only element": [1]
};
var failTestCases = {
    "remove index 0 or 1": [0, -1, 1, 2],
    "remove any index, all increasing": [1, 2, 5, 5, 5],
    "remove any index, with decrease": [1, 0],
    "one decrease": [0, 1, 2, 0, 1],
    "two decreases": [1, 0, 2, 1],
    "no elements to remove": []
};

runTests(passTestCases, true, almostIncreasingSequence);
runTests(failTestCases, false, almostIncreasingSequence);

function runTests(testCases, expectedResult, method) {
    console.log("\nShould Return " + expectedResult);
    for(var key in testCases)
    {
        var testCase = testCases[key];
        var result = method(testCase);
        console.log(key + ": " + testCase + ": result " + result); 
    }
}

On optimizing for speed:

This method will only make one pass through the array, while the original post uses nested loops. In general, a linear algorithm will be faster than a non-linear algorithm for large data sets.

Comparing the speeds of the two algorithms with these tiny test cases gives inconclusive results.