I came up with a solution but it does not perform well enough to pass with very large inputs. Any way of maybe doing it without iterating?

Challange: 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.

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.

Example

For sequence = [1, 3, 2, 1], the output should be solution(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 solution(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

[execution time limit] 4 seconds (py3)

[input] array.integer sequence

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

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

My solution is below and it seems to work however it does not perform well enough with very large inputs to count as a solution.

My Solution:

def solution(sequence):
    for number in range(len(sequence)):
        shortened = sequence.copy()
        shortened.pop(number)
        if len(shortened) == len(set(shortened)):
            if shortened == sorted(shortened):
                return True
    return False

CodePudding user response：

You will have to iterate the sequence no matter what. However, your code is performing slowly because, for each iteration, you are:

1. Copying the sequence
2. You're copying it again into a set
3. You're comparing it to the shortened array
4. You're sorting the shortened array

The key to this challenge is realizing you can solve this problem in O(n) by applying the following intuition:

For any a_i in the sequence, if a_i >= a_(i-1) then remove, if already removed, then false

You can construct an algorithm like:

bool removed = false;    
for(int i=1; i<sequence_length; i  ){
  if(sequence[i] >= sequence[i-1]){
    if(removed){
      return false;
    } else {
      removed = true;
    }
  }
}
return true;

CodePudding user response：

I don't think the problem is with the iteration O(n). There is no way to do it without reading every element. However you have other hidden iterations. copy O(n) (results in O(n²), when combined with the outer loop ). And sorted O(nlogn) (results in O(n²logn) when combined with outer loop).

Remove the inner complexity. My instinct says it can be done in O(n).