Finding an increasing sequence from a given array in a time-efficient manner in Python Problem Statement:


  Given a sequence of integers as an array, we have to 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;
  
  Since 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].


I have formulated a solution for this which is as follows:

def almostIncreasingSequence(sequence):
    j=0
    k=0
    i=1
    m=1
    jflag=0
    kflag=0

    dupsequence = list(sequence)

    while i &lt; len(sequence):
        difference = sequence[i]-sequence[i-1]
        if (difference) &lt;= 0:
            j = j+1
            del sequence[i]
            i = 0
            if j &gt; 1:
               jflag = 1
               break

        i = i + 1

    while m &lt; len(dupsequence):
        if (dupsequence[m]-dupsequence[m-1]) &lt;= 0:
            k = k+1
            del dupsequence[m-1]
            m = 0
            if k &gt; 1:
                kflag = 1
                break

        m = m + 1

    if kflag == 0 or jflag == 0:
        return True

    if jflag ==1 and kflag==1:
        return False


It is working and when I try to run the above code on the stress tests provided in this link, especially the test: 26 is taking 167 milliseconds.

I tried to profile using this piece of code:

def timex():
    return time()*1000

def main():
    starttime = timex()
    almostIncreasingSequence(sequence)
    endtime = timex()
    print 'timetaken to execute is %d milliseconds' %(endtime-starttime)

if __name__ == '__main__':
    main()



  timetaken to execute is 167 milliseconds




I'm asking for a more performance and resource efficient implementation. I'm also an amateur in Python.
I have done this challange before and I quite liked it, now let's dive in teh codez...

Review of your code:

First of all those 2 while loops look kind of silly, and that is what is giving you your TLE's, if you wanted to improve the timing on your code, I would start there.

This should be possible with a 1 loop, now when for instance you look at the last test... one of the last elements needs to be changed. You change it, and it works... but then you loop through the entire array again i = 0 means we start checking from beginning which is not needed. And after that you check the array yet again but this time delete another part and loop through it again! After your second loop finishes you check the outcome and that is a little too late.


I would use 1 loop, to check where the array is not strictly
increasing, afterwards remove at 2 different possitions (with list
comprehension) and check if those are strictly increasing.
Or don't start at position 0 if you found a not increasing bit


Some other PEP8 improvements


Missing whitespace around operator i=0 should be i = 0
if var == False: could be rewritten as if not var:
if var == True and var2 == True: could be rewritten as if var and var2:


A better way of handling this, I explain below



Alternative:

Let's break down the problem statement:


  Given a sequence of integers as an array, we have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.


Which means our algorithm should be doing 2 things:


Checking if a list is increasing sequence
Removing item in list and check again




Ok first make a function to check if a list is in a sequence and if not return the first element where it is not strictly increasing

def check_increasing(seq):
    # This will check if it is increasing:
    # If it is return -1 else return the element at which is it not increasing
    for i in range(len(seq)-1):
        if seq[i] &gt;= seq[i+1]:
            return i
    return -1


Well this is part 1 of the problem statement, Part 2 becomes simple if we re-use this function.

def almostIncreasingSequence(sequence):
    check = check_increasing(sequence)
    # List is increasing
    if check == -1:
        return True


We need to remove at most one element from the list, so if it is already strictly increasing we can return true, since no element has to be removed

If it is not we will continou, what are the possibilites from here?


If we delete earlier element, it becomes sctrictly increasing
If we delete later element, it becomes strictly increasing
If both are untrue,  we now that more than 1 element must be changed to form a strictly increasing sequence


Which in code translates to:

# Check if removing an item will make a strictly increasing list
if check_increasing(sequence[check-1:check] + sequence[check+1:]) == -1 or 
   check_increasing(sequence[check:check+1] + sequence[check+2:]) == -1:
    return True
# If not return False, since more than 1 element needs to be removed
return False




Making our final code like this

def check_increasing(seq):
    # This will check if it is increasing:
    # If it is return -1 else return the element at which is it not increasing
    for i in range(len(seq)-1):
        if seq[i] &gt;= seq[i+1]:
            return i
    return -1

def almostIncreasingSequence(sequence):
    check = check_increasing(sequence)
    # List is increasing
    if check == -1:
        return True
    # Check if removing an item will make a strictly increasing list
    if check_increasing(sequence[check-1:check] + sequence[check+1:]) == -1 or check_increasing(sequence[check:check+1] + sequence[check+2:]) == -1:
        return True
    # If not return False, since more than 1 element needs to be removed
    return False




Edit

Sorry but that test keeps breaking my IDLE, 
But here proof... no TLE on CodeFights: