CODEWITHSUNDEEP
javascriptoptimizationsequence
Lexxidon
Lexxidon

Reputation: 13

Make a Sequential Check faster

My challenge is the following:

I receive an unsorted array, and I need to tell if by removing one (and only one) element from that array, can I make it a strictly increasing sequence?

Note: sequence a0, a1, ..., an is considered to be a strictly increasing if a0 < a1 < ... < an. Sequence containing only one element is also considered to be strictly increasing.

So for example, [1,3,5,1,7] returns true, but [1,78, 23, 42, 102] returns false.

I was able to write a code that perfectly tests this, as you'll see below. The issue is, its' execution time is bigger than 4s (my execution time limit) if you provide it with a very big array.

I ran out of ideas and can't think about how I can improve this. Any tips are appreciated.

Edit: I realized that what is probably causing the issue is the spread operator I'm using to recreate the string every time I check it. But I can't think of any way I could not use it... Maybe tomorrow with a fresh head.

const isBigger = (a,b) => b > a;
const checksSequence = function (array) {
    isItaSequence = true;
    for(let i=0; i !== array.length - 1 && isItaSequence; i++ ){
        isItaSequence = isBigger(array[i],array[i+1]);     
    }
    return isItaSequence
}


function solution(sequence) {
    let sequenceRemoving1 = false;
    for (let i = 0; i !== sequence.length && !sequenceRemoving1 ; i++){
    let modifiedArray = [...sequence]
    modifiedArray.splice(i, 1)
    sequenceRemoving1 = checksSequence(modifiedArray);
    }
    return sequenceRemoving1 
}
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <script src="index.js"></script>
</head>
<body>
    
</body>
</html>

Upvotes: 0

Views: 34

Answers (1)

sashok1337
sashok1337

Reputation: 1019

You have a lot of nested loops, so the complexity of the algorithm is very high. Try next code:

const t = [1, 3, 5, 1, 7];
const t1 = [10, 1, 2, 3, 4, 5];
const t2 = [3, 1, 4, 5, 6, 7];

const f = [1, 78, 23, 42, 102];
const f1 = [1, 1, 2, 3, 4, 4];
const f2 = [1, 1, 1, 2, 3];

console.log(solution(t), solution(t1), solution(t2), solution(f), solution(f1), solution(f2));

function solution(array) {
    let max = array[0];
    let firstOccurrence = false;

    for (let i = 1; i < array.length; i++) {
        if (max >= array[i]) {
            if (firstOccurrence) {
                return false;
            }

            firstOccurrence = true;
            if (i === 1) {
                max = array[i];
            }
        } else {
            max = array[i];
        }
    }

    return true;
}

Upvotes: 1

Related Questions