# JavaScript Determine if Array has Almost Increasing Sequence

A coding challenge on a website says to determine if an array would have an increasing sequence if one element were removed from that array.

Here is the function:

const almostIncreasingSequence = sequence => {
const increasingSequence = arr => {
for (let i = 0; i < arr.length; i++) {
if (arr[i - 1] >= arr[i]) {
return false;
}
}
return true;
};
for (let i = 0; i < sequence.length; i++) {
const left = sequence.slice(0, i);
const right = sequence.slice(i + 1);
const newArr = left.concat(right);
if (increasingSequence(newArr)) {
return true;
}
}
return false;
};


The function produces the exact same output as all of the visible tests on the site:

var toTest = [
[1, 3, 2, 1],
[1, 3, 2],
[1, 2, 1, 2],
[1, 4, 10, 4, 2],
[10, 1, 2, 3, 4, 5],
[1, 1, 1, 2, 3],
[0, -2, 5, 6],
[1, 2, 3, 4, 5, 3, 5, 6],
[40, 50, 60, 10, 20, 30],
[1, 1],
[1, 2, 5, 3, 5],
[1, 2, 5, 5, 5],
[10, 1, 2, 3, 4, 5, 6, 1],
[1, 2, 3, 4, 3, 6],
[1, 2, 3, 4, 99, 5, 6],
[123, -17, -5, 1, 2, 3, 12, 43, 45],
[3, 5, 67, 98, 3]
];

for (let i = 0; i < toTest.length; i++) {
console.log(almostIncreasingSequence(toTest[i]));
}


Outputs:

false
true
false
false
true
false
true
false
false
true
true
false
false
true
true
true
true


But then a hidden error triggers upon submission telling me that the execution time is longer than the maximum of 4 seconds. How can I improve the time complexity of this algorithm?

• Not an answer, because my answer is not to use this algorithm. This algorithm is O(n2) [almost, the early returns in the function help], but the problem can be solved O(n). I am not a javascript coder, so cannot provide any particular advice on this algorithm. – AJD Jul 6 '18 at 21:39
• Now that I think about it I could just iterate over the array and just return false if the item at i-1 is greater than or equal to the item at i+1. – NewbieWanKenobi Jul 6 '18 at 22:07
• @SeanValdiva: Close. Just iterate over the array and count if the item at i-1is greater than or equal to the item at i. Couple of options. Complete the loop, return the count and then return false if count>1. Or break the loop and return false if count>1 (return true otherwise). With your solution, firstly you are comparing the wrong two elements, and you are returning false at the first instance, not the second instance. – AJD Jul 6 '18 at 22:16
• @SeanValdiva: Because we only need to know if it would be ascending if we remove one item. We don't have to remove the item! With your 2-step (-1,+1) method, you are not checking the item in between and you could get inconsistent results - I haven't followed that logic all the way through, but keep it simple and direct. But you see a difference in approach? You are asking what happens if we have removed something, I am asking if we can remove something. – AJD Jul 6 '18 at 22:26
• @AJD Your algorithm will return a false positive for e.g. 4,5,6,1,2,3. – vnp Jul 6 '18 at 23:31

Your code has complexity $O(N^2)$ (with $N$ being the array length), and also creates up to $N$ temporary arrays.

Also note that your increasingSequence function accesses arr[-1], the loop should start with let i = 1.

As already mentioned in the comments, the result can be obtained with a single traversal of the array, thus reducing the complexity to $O(N)$, and without additional storage.

The idea is to find the first element violating the (strict) increasing condition, i.e. the first index i with a[i - 1] >= a[i]. Then one of a[i-1] or a[i] must be removed, and both cases can occur, as the following examples show:

a = [ 4, 9, 5, 6, 7 ], i = 2  -->  remove a[i - 1] = 9
a = [ 4, 5, 1, 6, 7 ], i = 2  -->  remove a[i] = 1


Therefore we check if

a[i - 2], a[i - 1], a[i], a[i + 1]


can be made strictly increasing by removing one of the middle elements.

Since no more elements can be removed, the remaining elements, starting at index i + 1, must be strictly increasing.

There are also some shortcuts, e.g. if the array has at most 2 elements, or if the “first decrease” is at the end of the array.

An implementation could look like this (it gives the correct result in all your test cases):

const almostIncreasingSequence = a => {
if (a.length <= 2) {
return true;
}

// Find first i such that a[i - 1] >= a[i]:
let i = 1;
while (i < a.length - 1 && a[i - 1] < a[i]) {
i++;
}
if (i >= a.length - 1) {
return true; // Increasing if last element is removed.
}

// Can a[i - 1] be removed ?
let case1 = (i == 1 || a[i - 2] < a[i]) && a[i] < a[i + 1];
// Can a[i] be removed ?
let case2 = a[i - 1] < a[i + 1];

if (!case1 && !case2) {
return false;
}

// Check that a[i + 1], ... is increasing.
for (let j = i + 2; j < a.length; j++) {
if (a[j - 1] >= a[j]) {
return false;
}
}

return true;
};


(JavaScript is not my first language, so take this just as a suggestion, it surely can be implemented in a more idiomatic way.)