Determine if the input list is strictly increasing

Question

I am trying to figure out if an input list is a strictly increasing list. Moreover, If removing only one element from the list results in a strictly increasing list, we still consider the list true. Here is my code. It seems to have an index error, but I do not understand why.

 def almostIncreasingSequence(sequence):
    n=len(sequence)
    count=0
    if n<=2:
        return True

    for i in range (n-1):
        #test if the i-th element is bigger or equal to the elements after it. If it is, remove that element, and add one to count 
        for j in range (i+1,n):
            if sequence[i]>=sequence[j]:
                sequence.pop(i)
                count+=1
    #if there is more than one element that has to be taken out, it's false           
    if count>1:
        return False

    return True

Answer 1

Alright, so it turns out this problem is not that easy.

If you want an efficient solution, I think your best bet may be an algorithm similar to the longest increasing subsequence problem.

But here, we don't care about the actual longest increasing subsequence - we just need it's length. Also, we can short-circuit when maintaining our ordered list if we have had to perform n insertions already (where n is our restriction on the number of "out of order" elements).

This also generalizes very well to the n element "almost increasing" case, and in the worst case performs n-1 binary searches on lists of size M-n-1 to M, where M is the size of the list.

import bisect

def almost_increasing(li, n=1):
    if len(li) < 2:
        return True
    ordered_li = [li[0]]
    violator_count = 0
    for ele in li[1:]:
        if ele < ordered_li[0]:
            violator_count += 1
            ordered_li[0] = ele
        elif ele > ordered_li[-1]:
            ordered_li.append(ele)
        else:
            violator_count += 1
            insertion_pos = bisect.bisect_right(ordered_li, ele)
            ordered_li[insertion_pos] = ele
        if violator_count > n: return False
    return True

The idea behind this algorithm is as follows:

• We move through the list, and maintain an ordered subsequence of our list all the while.

• When we reach a new element

  • if that element cannot be appended onto our ordered subsequence, it is a "violator" of the increasing property. We subsequently insert it into the ordered subsequence in the correct position, using bisect for binary search.

  • otherwise, we just append it to our ordered subsequence and continue on.

• At the end of each iteration, if we have too many violators already we can short-circuit out. Otherwise, after the loop is done we are guaranteed to have an increasing subsequence that has length within n of the length of our original list.

---

Demo

>>> almost_increasing([5, 1, 2, 3, 4])
True
>>> almost_increasing([1, 2, 5, 2, 15, 0, 176])
False
>>> almost_increasing([1, 2, 5, 2, 15, 0, 176], 2)
True