javascript - Determine whether array holds an almost increasing sequence

Question

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.

For sequence = [1, 3, 2, 1], the output should be

almostIncreasingSequence(sequence) === false

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be

almostIncreasingSequence(sequence) === true

As you can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Here is what I have so far:

function almostIncreasingSequence(sequence) {
  //compare current int to previous, return true if greater than 
  //remove int at index and compare with new values, return false if comparison fails
  var result = false;

  for(var i = 0; i < sequence.length; i++){
     var newSequence = sequence.slice();
     var subSequence = newSequence.splice(i, 1);

     for(var j = 0; j < newSequence.length - 1; j++){
        if(newSequence === newSequence.sort((a,b) => a < b).reverse()){
          result = true;
        } 
     }         
  }
  return result;
}

I'm trying to figure out how to solve this problem. I feel like I'm very close but for some reason when I call reverse in the conditional statement it also sorts out the newSequence variable. It's sorting two variables in the conditional, not one. As a result it resolves to true. I'm not clear why this is happening. Any feedback is appreciated.

Answer 1

There is no need to use a nested loop, nor to create new arrays. This can be done in O(n) time:

function almostIncreasingSequence(sequence) {
    var prev = -Infinity,
        beforePrev = -Infinity,
        allowExceptions = true;
    
    for (var curr of sequence) {
        // Is order not maintained?
        if (curr <= prev) {
            // Give up when this is not the first exception
            if (!allowExceptions) return false;
            allowExceptions = false;
            // Decide whether to skip the current or previous value
            if (curr > beforePrev) prev = curr;
        } else { // Normal case: keep track of two preceding values
            beforePrev = prev;
            prev = curr;
        }
    }
    return true;
}

console.log(almostIncreasingSequence([1,5,3,4,8])); // true
console.log(almostIncreasingSequence([1,5,0,6,8])); // true
console.log(almostIncreasingSequence([1,5,0,4,8])); // false