My 'almostIncreasingSequence(sequence)' code is too slow for lists that have 10000+ elements. [CodeSignal]

Question

I asked this question on Stackoverflow as well, but I think it's best suited here because my code needs optimization instead of error checking (that I previously thought).

I've made changes to my code as well. But the logic is pretty much the same:

• My code first checks the length of the provided sequence, if it is 2 or less it automatically returns True.
• Next, it creates a newlist with the first element removed and checks if the rest of the list is in ascending order.
• If the sequence is not in order, the iteration breaks and a newlist is generated again and this time with the next element removed.
• This continues until there are no more elements to remove (i.e. i == len(sequence) - 1), which ultimately returns as False
• If in any of the iterations, the list is found to be in ascending order(i.e. in_order remains True), the function returns True.

def almostIncreasingSequence(sequence):
    # return True for lists with 2 or less elements.
    if len(sequence) <= 2:
        return True

    # Outerloop, removes i-th element from sequence at each iteration
    for i in range(len(sequence)):
        newlist = sequence[:i] + sequence[i+1:]

        # Innerloop, checks if the sequence is in ascending order
        j = 0
        in_order = True
        while j < len(newlist) - 1:
            if newlist[j+1] <= newlist[j]:
                in_order = False
                break
            j += 1
        if in_order == True:
            return True
        elif i == len(sequence)-1:
            return False
 
        

---

I received a suggestion that I should only use one loop, but I cannot think of a way to implement that. Nested loops seems necessary because of the following assumptions:

1. I have to remove every next element from the original sequence. (outer loop)
2. I need to check if all the elements are in order. (inner loop)

This is a brief on almostIncreasingSequence() my code follows the logic provided in the answer here, it solves almost all of the Tests as well, but it is too slow for larger lists (that are approx 10000+ elements).

Answer 1

Checking if a list is strictly increasing

The inner loop checks if a list (in this case newList) is strictly increasing:

j = 0
in_order = True
while j < len(newlist) - 1:
    if newlist[j+1] <= newlist[j]:
        in_order = False
        break
    j += 1
if in_order == True:
    return True

1. In general variable names should use underscores, so newlist becomes new_list. PEP 8.
2. It can be simplified with a for-else:

for j in range(len(new_list) - 1):
    if new_list[j+1] <= new_list[j]:
        break
else:
    return True

Or using all:

if all(new_list[i] > new_list[i - 1] for i in range(1, len(new_list))):
    return True

Optimization

As you said, the solution is too slow for large input due to the inner loop that runs every time, making the overall complexity \$O(n^2)\$.

The current solution follows this approach:

1. For each element of the input list
2. Build a new list without such element and check if strictly increasing

Consider simplifying the approach like the following:

1. Find the first pair that is not strictly increasing
2. Build a new list without the first element of the pair and check if it is increasing
3. Build a new list without the second element of the pair and check if it is increasing

For example:

def almostIncreasingSequence(sequence):
    def is_increasing(l):
        return all(l[i] > l[i - 1] for i in range(1, len(l)))

    if is_increasing(sequence):
        return True

    # Find non-increasing pair
    left, right = 0, 0
    for i in range(len(sequence) - 1):
        if sequence[i] >= sequence[i + 1]:
            left, right = i, i + 1
            break

    # Remove left element and check if it is strictly increasing
    if is_increasing(sequence[:left] + sequence[right:]):
        return True

    # Remove right element and check if it is strictly increasing
    if is_increasing(sequence[:right] + sequence[right + 1:]):
        return True

    return False

I believe there should be an approach that doesn't build the two additional lists to reduce the space complexity, but I'll leave that to you.