JavaScript Determine if Array has Almost Increasing Sequence

Question

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?

Answer 1

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