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

Question

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 < len(sequence):
        difference = sequence[i]-sequence[i-1]
        if (difference) <= 0:
            j = j+1
            del sequence[i]
            i = 0
            if j > 1:
               jflag = 1
               break

        i = i + 1

    while m < len(dupsequence):
        if (dupsequence[m]-dupsequence[m-1]) <= 0:
            k = k+1
            del dupsequence[m-1]
            m = 0
            if k > 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.

Answer 1

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:

1. Checking if a list is increasing sequence
2. 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] >= 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] >= 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:

Answer 2

I'll second @Ludisposed's comment: you're looping too much.

Have a look at this code:

while i < len(sequence):
    difference = sequence[i]-sequence[i-1]
    if (difference) <= 0:
        j = j+1
        del sequence[i]
        i = 0
        if j > 1:
           jflag = 1
           break

    i = i + 1

Consider a sequence that has a subset like this: [..., 3, 5, 4, 6, ...]

You process this in your loop, until sequence[i] is 4. Then, difference is 4 - 5 == -1. So the if code executes, and you del sequence[i].

Now you reset i to zero and loop some more.

What if there are 1 million values in the sequence before the 3?

You know they're valid - your loop scanned over them. The only things you need to worry about are the values in the "local window." What's the local window for this loop? sequence[i] and sequence[i-1].

Given that you deleted sequence[i] you can expect that sequence[i+1] got moved down, so the value of sequence[i] has changed. But sequence[i-1] has not changed - the del sequence[i] didn't affect that value.

What should you do? Reset your i value to some value other than zero. I think you should reset it down by 1: i -= 1. Then your increment at the bottom will bring it back up, and you'll repeat the check for the same sequence[i] (which has a new value thanks to the del statement).

This should allow you to avoid re-scanning any good values in the early part of the list, which will likely shave some time off your hard conditions.