almostIncreasingSequence - Javascript

Question

Hi guys I'm using Codefights concurrently while I learn algorithims & data structures and I cant seem to solve this problem.

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.

My code is failing due to performance and I have a general idea why considering my copying of the original array and looping through both. But I am unable to think of a more optimized way.

function almostIncreasingSequence(sequence) {
    let result = false;
    for(let i = 0; i < sequence.length; i++) {
        let newSequence = [...sequence]
        newSequence.splice(i,1)
        result = isArraySequential(newSequence)
        if (result) {
            return result;
        }
    }
        return result;
}

function isArraySequential(array) {
    let isSequential = true;
    for(let i = 0; i < array.length; i++) {
        if(i == array.length - 1) {return isSequential}
         if (array[i + 1] < array[i] || array[i + 1] == array[i]) {
            return !isSequential;
        }
    }
}

Answer 1

You don't need to constantly check the entire array, nor use multiple loops.

The problem can be broken down to smaller questions. For each element in the list...

• Is the current element greater than the last (increasing)?
  • Yes...
    • Good! We don't need to do anything.
  • No...
    • Has this happened already? If so, it's not almost increasing.
    • If we remove the previous item, are the surrounding items fixed?
    • No? What if we remove the current item instead?
    • Still no? Then that means we can't solve this in one move. It's not almost increasing.

The code would look something like this:

function almostIncreasingSequence(sequence) {
  let invalidItemsCount = 0;
  
  for (let i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[i-1]) {
      invalidItemsCount++;
      if (invalidItemsCount > 1) return false;
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
    }
  }
  
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));

Commented version:

function almostIncreasingSequence(sequence) {
  //Keep track of how many replacements we've had to make
  let invalidItemsCount = 0;
  
  //Start our loop at 1 so that [i-1] doesn't refer to index "-1"
  for (let i = 1; i < sequence.length; i++) {
  
    //If this item is not increasing, we'll need to address it
    if (sequence[i] <= sequence[i-1]) {
    
      //Increment our invalidItemsCount
      invalidItemsCount++;               
      
      //If this is our second invalidItem, then it's not almost increasing.
      if (invalidItemsCount > 1) return false;  
      
      //If removing the previous element doesn't help, and removing the current item doesn't help,
      //then we can't solve this in one move. It's not almost increasing.
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
      
    }
  }
  
  //We've made it through the entire loop without fail. This is almost increasing.
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));