1
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – AJD Jul 6 '18 at 21:39
  • \$\begingroup\$ 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. \$\endgroup\$ – NewbieWanKenobi Jul 6 '18 at 22:07
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – AJD Jul 6 '18 at 22:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – AJD Jul 6 '18 at 22:26
  • 1
    \$\begingroup\$ @AJD Your algorithm will return a false positive for e.g. 4,5,6,1,2,3. \$\endgroup\$ – vnp Jul 6 '18 at 23:31
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.