how can I make this faster. By removing one element from an array, check if array is increasing seuence

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.

Example

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.

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].

[input] array.integer sequence

Guaranteed constraints: 2 ≤ sequence.length ≤ 105, -105 ≤ sequence[i] ≤ 105.

[output] boolean

function almostIncreasingSequence(arr) {

for (let i = 0; i < arr.length; i++) {
    if (isSeq(arr.slice(0, i).concat(arr.slice(i + 1)))) {
        return true;
        break;
    }

}
return false

}

function isSeq(subseq) {
    var sliced1 = subseq.slice(0, subseq.length - 1);
    var sliced2 = subseq.slice(1);
    return sliced1.every((el, index) => el < sliced2[index])

 }

My code is slow. How can be improved.

Answer 1

I have a difference approach.

• First we need to find all strictly increasing sub-sequences inside our array
  • If we find one strictly increasing sub-sequence, then everything is great :)
  • Else if we find more than two strictly increasing sub-sequence: then we would need to remove at least TWO elements from our array to make one strictly increasing sequence
  • Else (now we have TWO strictly increasing sub-sequence): Check if by removing the last element from the first sub-sequence and then joining it with the second sub-sequence, we would have an strictly increasing sequence. If not, then check if by removing the first element from the second sub-sequence and then joining it with the first sub-sequence, we would have an strictly increasing sequence. If not, then we CAN'T.

function almostIncreasingSequence(arr) {
    function nextSeq(fromIndex, res) {
        res.push(arr[fromIndex])
        var i=fromIndex+1
        for (;i<arr.length;++i) {
            if (arr[i] > arr[i-1]) {
                res.push(arr[i])
            } else {
                break;
            }
        }
        return i
    }
    function isSeq(x) {
        if (x.length === 1) {
            return true
        }
        for (var i=1;i<x.length;++i) {
            if (x[i] <= x[i-1]) {
                return false
            }
        }
        return true
    }
    function concat(x1, x2) {
        const res = []
        for (var i=0;i<x1.length;++i) {
            res.push(x1[i])
        }
        for (var i=0;i<x2.length;++i) {
            res.push(x2[i])
        }
        return res
    }
    function sub(x, fromIndex, length) {
        const res = []
        for (var i=fromIndex;i<fromIndex + length;++i) {
            res.push(x[i])
        }
        return res
    }
    var index = 0
    const k = []
    while (index < arr.length) {
        const x = []
        index = nextSeq(index, x)
        k.push({
            index: index,
            list: x
        })
    }
    if (k.length === 1) {
        return true
    } else if (k.length > 2) {
        return false
    } else {
        var x1 = sub(k[0].list, 0, k[0].list.length - 1)
        var x2 = k[1].list
        var x = concat(x1, x2)
        var ok = isSeq(x)
        if (ok) {
            return true
        }
        x1 = k[0].list
        x2 = sub(k[1].list, 1, k[1].list.length - 1)
        x = concat(x1, x2)
        ok = isSeq(x)
        return ok
    }
}
const testCases = [
  { array: [1, 3, 2], expected: true },
  { array: [1, 3, 2, 1], expected: false },
  { array: [1, 2, 1, 2], expected: false },
  { array: [3, 6, 5, 8, 10, 20, 15], expected: false },
  { array: [1, 1, 2, 3, 4, 4], expected: false },
  { array: [1, 4, 10, 4, 2], expected: false },
  { array: [10, 1, 2, 3, 4, 5], expected: true },
  { array: [1, 1, 1, 2, 3], expected: false },
  { array: [0, -2, 5, 6], expected: true },
  { array: [1, 2, 3, 4, 5, 3, 5, 6], expected: false },
]
testCases.forEach(a => {
    const res = almostIncreasingSequence(a.array)
    if (res === a.expected) {
        console.log('OK')
    } else {
        console.error(`${a.array.join(', ')} expected ${a.expected}!`)
    }
})

Answer 2

If it't this one (your link didn't work and answer isn't updated with requirements). Then the requirements are:

Given a sequence of integers, check whether it is possible to obtain a strictly increasing sequence by erasing no more than one element from it.

This turned out to be trickier than expected. Had some time to work out some failing edge cases but can't actually test on codewars or codefights because the links won't load without server errors.

Pass a checkFunction into a function that will check sequence (array) this checkFunction will receive current element in array and next element. In our case checkFunction will check if current element is smaller than next element:

const increasing = isInSequence((current,next)=>current<next);

That uses the return value of isInSequece which is a partially applied function with the checkFunction set to a function checking current element smaller than next.

If checkFunction fails then there are 4 situations:

1. [1,2,3,2] Last and second last element fails, just remove the last element
2. [1,10,2,3] If current index is 1 (the number 10) then current would be checked with 2 and fail. Removing 10 (current) would be best.
3. [1,2,0,3] If current index is 1 (the number 2) then 2 would be checked with 0 and fail. Removing 0 would be best not the current number but the next
4. [2,1,2,3] First and second element fails, just remove first.

Situation 1 and 4 does not need the checkFunction as the decision of what number to remove can be made depending on the currentIndex and array.length. In situation 2 and 3 the checkFunction is used with previous and next value to determine if it's best to remove the current or the next item:

//compare A with C in ABC where A is previous, B is current and C is next
//  we just failed to compare current with next (B with C)
array=(checkFunction(array[currentIndex-1],array[next]))
  //A with C passed, get rid of B
  ? [array[currentIndex-1]].concat(array.slice(next))
  //A with C failed, get rid of C (A with B passed)
  : [array[currentIndex]].concat(array.slice(next+1))

Here is the whole code:

const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    if(currentIndex>=array.length-1) return true;//there is no next index to copare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      missed++;
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex-1>=0) {
        //compare A with C in ABC where A is previous, B is current and C is next
        //  we just failed to compare current with next (B with C)
        array=(checkFunction(array[currentIndex-1],array[next]))
          //A with C passed, get rid of B
          ? [array[currentIndex-1]].concat(array.slice(next))
          //A with C failed, get rid of C (A with B passed)
          : [array[currentIndex]].concat(array.slice(next+1))
      }else{
        //There is no previous element from current so remove current
        array = array.slice(currentIndex);
      }
      next = 0;
    }
    if(missed>maxMissed){
      return false;//too many misses, return false
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(false,increasing([3,2],0),"3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");

The following code I've added for completeness since my code takes a maxMissed that can be higher than 1. In your case you can only miss one but if you can have more than one misses the following case would wrongfully fail [0,1,100,101,2,3,4,5] with 2 misses allowed:

const showDebug = false;
const debugLog = function(){
  if(showDebug){
    console.log.apply(window,Array.from(arguments));
  }
}
const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    debugLog("array:",array,"missed:",missed,"index:",currentIndex);
    if(currentIndex>=array.length-1) return true;//there is no next index to compare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      debugLog("------------miss");
      missed++
      if(missed>maxMissed){
        return false;//too many misses, return false
      }
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex===0) {
        //There is no previous element from current so remove current
        array = array.slice(currentIndex+1);
      }else{
        //try again with current or next element removed, if either returns true
        //  then return true
        return recur(
          missed,0,array.slice(0,currentIndex).concat(array.slice(currentIndex+1))
        ) || recur(
          missed,0,array.slice(0,next).concat(array.slice(next+1))
        )
      }
      next = 0;
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([3,2,3],1),"3,2,3 should return true");
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");
test(false,increasing([3,2],0),"3,2 should return false");

// less performant version to fix this edge case (not your problem since only 1 can fail in your case)
test(true,increasing([0,1,100,101,2,3,4,5],2),"0,1,100,101,2,3,4,5 should return true (can miss two)");

Answer 3

Your solution is creating new arrays when you use slice() which is more time consuming. To solve the problem you just need to check if arr[x] > arr[x+1] is true twice. You shouldn't need to modify the array.

let count = 0, highest = 0;
for(let x=0; x < arr.length - 1; x++) {
     highest = Math.max(highest, arr[x]);
     if(highest > arr[x+1]) {
        if(++count === 2) {
           return false;
        }
     }
}
return true;