javascript: how to make function run faster

Viewed 826

so i have to write a function which meets the following requirements:

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/Output

[time limit] 4000ms (js)
[input] array.integer sequence

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

so my code works except for one problem--there are 30 tests it has to pass with the time constraint of 4000ms, but it always times out on the 30th test, every time. i have tried modifying it so that it runs faster, but each time i do so it no longer works correctly. although i technically only have to write one function, i broke it up into three separate functions. here's my code:

var greater = function(a, b) {
  if (a < b) {
    return true
  } else {
    return false
  }
}

function greaterThan(arr) {
  for (var i = 0; i < arr.length-1; i++) {
    var curr = arr[i]
    var next = arr[i + 1]
    if (greater(curr, next) === false) {
      return false
    }
  }
  return true
}

function almostIncreasingSequence(sequence) {
  for(var i = 0; i < sequence.length; i++) {
    var newArr = sequence.slice()
    newArr.splice(i, 1)
    if (greaterThan(newArr) === true) {
      return true
    } 
  }
  return false
}

so how can i make it run faster without using two for-loops/iterations to do this?

1 Answers
Related