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.
Example
For sequence [1, 3, 2, 1]
, the output should be:
almostIncreasingSequence(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:
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].
My code:
def almostIncreasingSequence(sequence):
c= 0
for i in range(len(sequence)-1):
if sequence[i]>=sequence[i+1]:
c +=1
return c<1
But it can't pass all tests.
input: [1, 3, 2]
Output:false
Expected Output:true
Input: [10, 1, 2, 3, 4, 5]
Output: false
Expected Output: true
Input: [0, -2, 5, 6]
Output: false
Expected Output: true
input: [1, 1]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 3, 6]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 99, 5, 6]
Output: false
Expected Output: true
Your algorithm is much too simplistic. You have a right idea, checking consecutive pairs of elements that the earlier element is less than the later element, but more is required.
Make a routine first_bad_pair(sequence)
that checks the list that all pairs of elements are in order. If so, return the value -1
. Otherwise, return the index of the earlier element: this will be a value from 0
to n-2
. Then one algorithm that would work is to check the original list. If it works, fine, but if not try deleting the earlier or later offending elements. If either of those work, fine, otherwise not fine.
I can think of other algorithms but this one seems the most straightforward. If you do not like the up-to-two temporary lists that are made by combining two slices of the original list, the equivalent could be done with comparisons in the original list using more if
statements.
Here is Python code that passes all the tests you show.
def first_bad_pair(sequence):
"""Return the first index of a pair of elements where the earlier
element is not less than the later elements. If no such pair
exists, return -1."""
for i in range(len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
If you do want to avoid those temporary lists, here is other code that has a more complicated pair-checking routine.
def first_bad_pair(sequence, k):
"""Return the first index of a pair of elements in sequence[]
for indices k-1, k+1, k+2, k+3, ... where the earlier element is
not less than the later element. If no such pair exists, return -1."""
if 0 < k < len(sequence) - 1:
if sequence[k-1] >= sequence[k+1]:
return k-1
for i in range(k+1, len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence, -1)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence, j) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence, j+1) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
And here are the tests I used.
print('\nThese should be True.')
print(almostIncreasingSequence([]))
print(almostIncreasingSequence([1]))
print(almostIncreasingSequence([1, 2]))
print(almostIncreasingSequence([1, 2, 3]))
print(almostIncreasingSequence([1, 3, 2]))
print(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))
print(almostIncreasingSequence([0, -2, 5, 6]))
print(almostIncreasingSequence([1, 1]))
print(almostIncreasingSequence([1, 2, 3, 4, 3, 6]))
print(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))
print(almostIncreasingSequence([1, 2, 2, 3]))
print('\nThese should be False.')
print(almostIncreasingSequence([1, 3, 2, 1]))
print(almostIncreasingSequence([3, 2, 1]))
print(almostIncreasingSequence([1, 1, 1]))
This is mine. Hope you find this helpful:
def almostIncreasingSequence(sequence):
#Take out the edge cases
if len(sequence) <= 2:
return True
#Set up a new function to see if it's increasing sequence
def IncreasingSequence(test_sequence):
if len(test_sequence) == 2:
if test_sequence[0] < test_sequence[1]:
return True
else:
for i in range(0, len(test_sequence)-1):
if test_sequence[i] >= test_sequence[i+1]:
return False
else:
pass
return True
for i in range (0, len(sequence) - 1):
if sequence[i] >= sequence [i+1]:
#Either remove the current one or the next one
test_seq1 = sequence[:i] + sequence[i+1:]
test_seq2 = sequence[:i+1] + sequence[i+2:]
if IncreasingSequence(test_seq1) == True:
return True
elif IncreasingSequence(test_seq2) == True:
return True
else:
return False
The solution is close to the intuitive one, where you check if the current item in the sequence is greater than the current maximum value (which by definition is the previous item in a strictly increasing sequence).
The wrinkle is that in some scenarios you should remove the current item that violates the above, whilst in other scenarios you should remove previous larger item.
For example consider the following:
[1, 2, 5, 4, 6]
You check the sequence at item with value 4
and find it breaks the increasing sequence rule. In this example, it is obvious you should remove the previous item 5
, and it is important to consider why. The reason why is that the value 4
is greater than the "previous" maximum (the maximum value before 5
, which in this example is 2
), hence the 5
is the outlier and should be removed.
Next consider the following:
[1, 4, 5, 2, 6]
You check the sequence at item with value 2
and find it breaks the increasing sequence rule. In this example, 2
is not greater than the "previous" maximum of 4
hence 2
is the outlier and should be removed.
Now you might argue that the net effect of each scenario described above is the same - one item is removed from the sequence, which we can track with a counter.
The important distinction however is how you update the maximum
and previous_maximum
values:
For [1, 2, 5, 4, 6]
, because 5
is the outlier, 4
should become the new maximum
.
For [1, 4, 5, 2, 6]
, because 2
is the outlier, 5
should remain as the maximum
.
This distinction is critical in evaluating further items in the sequence, ensuring we correctly ignore the previous outlier.
Here is the solution based upon the above description (O(n)
complexity and O(1)
space):
def almostIncreasingSequence(sequence):
removed = 0
previous_maximum = maximum = float('-infinity')
for s in sequence:
if s > maximum:
# All good
previous_maximum = maximum
maximum = s
elif s > previous_maximum:
# Violation - remove current maximum outlier
removed += 1
maximum = s
else:
# Violation - remove current item outlier
removed += 1
if removed > 1:
return False
return True
We initially set the maximum
and previous_maximum
to -infinity
and define a counter removed
with value 0
.
The first test case is the "passing" case and simply updates the maximum
and previous_maximum
values.
The second test case is triggered when s <= maximum
and checks if s > previous_maximum
- if this is true, then the previous maximum
value is the outlier and is removed, with s
being updated to the new maximum
and the removed
counter incremented.
The third test case is triggered when s <= maximum
and s <= previous_maximum
- in this case, s
is the outlier, so s
is removed (no changes to maximum
and previous_maximum
) and the removed
counter incremented.
One edge case to consider is the following:
[10, 1, 2, 3, 4]
For this case, the first item is the outlier, but we only know this once we examine the second item (1
). At this point, maximum
is 10
whilst previous_maximum
is -infinity
, so 10
(or any sequence where the first item is larger than the second item) will be correctly identified as the outlier.
The reason why your modest algorithm fails here (apart from the missing '=' in return) is, it's just counting the elements which are greater than the next one and returning a result if that count is more than 1.
What's important in this is to look at the list after removing one element at a time from it, and confirm that it is still a sorted list.
My attempt at this is really short and works for all scenario. It fails the time constraint on the last hidden test set alone in the exercise.
As the problem name suggests, I directly wanted to compare the list to its sorted version, and handle the 'almost' case later - thus having the almostIncreasingSequence. i.e.:
if sequence==sorted(sequence):
.
.
But as the problem says:
determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array (at a time).
I started visualizing the list by removing an element at a time during iteration, and check if the rest of the list is a sorted version of itself. Thus bringing me to this:
for i in range(len(sequence)):
temp=sequence.copy()
del temp[i]
if temp==sorted(temp):
.
.
It was here when I could see that if this condition is true for the full list, then we have what is required - an almostIncreasingSequence! So I completed my code this way:
def almostIncreasingSequence(sequence):
t=0
for i in range(len(sequence)):
temp=sequence.copy()
del temp[i]
if temp==sorted(temp):
t+=1
return(True if t>0 else False)
This solution still fails on lists such as [1, 1, 1, 2, 3]. As @rory-daulton noted in his comments, we need to differentiate between a 'sorted' and an 'increasingSequence' in this problem. While the test [1, 1, 1, 2, 3] is sorted, its on an increasingSequence as demanded in the problem. To handle this, following is the final code with a one line condition added to check for consecutive same numbers:
def almostIncreasingSequence(sequence):
t=0
for i in range(len(sequence)):
temp=sequence.copy()
del temp[i]
if temp==sorted(temp) and not(any(i==j for i,j in zip(sorted(temp), sorted(temp)[1:]))):
t+=1
return t>0
As this still fails the execution time limit on the last of the test (the list must be really big), I am still looking if there is a way to optimize this solution of mine.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With