I came across an interesting question in Code Signal.
"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."
It is strictly increasing if every element in the array is greater than its successor.
For a strictly increasing sequence we can check for each element whether it is greater than the next. In that case we can come to a conclusion that this sequence is not strictly increasing. If every element is greater than the successor we get to know it is a strictly increasing.
For worst case(The sequence is strictly increasing), the algorithmic complexity is O(n).
If we use similar approach for the question, we have to remove each element and pass the sequence to the above function.
So for n elements, we use a function with a complexity of O(n). Therefore this approach will have a complexity of O(n^2). The complexity is more here and so i am trying to reduce it in the consequent steps.
I will devise a divide and conquer method to solve the problem with lesser complexity. We can think of 'strict increase' as a staircase with stairs of different heights. When climbing every stairs are higher than the preceding one. Our condition (Remove one number to get strict increase) will be like removing one stone in the stairs to make it strictly increase.
So whenever we find an element greater than or equal to its successor, then we have to first verify staircase condition. If the element before is also greater than the successor of the element, then even if we remove the stone, we will not get the stair case (strictly increasing). In that case we can say it is not almost increasing strictly!
In case if that is not the case we can go on to search for another stone in our path. If we find another stone(n=2), then we do not have an option to move further. (since we can only remove one number!). So we are a super mario without life and have to confirm that the sequence is not almost increasing strictly.
In case we do not find any stone or only one stone (n=0 or 1), then we can climb till the end! So then the sequence is almost strictly increasing!
In this algorithm, the worst case is when it return True. Every element is compared with its successive elements and control flows out of the loop. So the algorithmic complexity will be O(n).
I will devise a divide and conquer method to solve the problem with lesser complexity. We can think of 'strict increase' as a staircase with stairs of different heights. When climbing every stairs are higher than the preceding one. Our condition (Remove one number to get strict increase) will be like removing one stone in the stairs to make it strictly increase.
So whenever we find an element greater than or equal to its successor, then we have to first verify staircase condition. If the element before is also greater than the successor of the element, then even if we remove the stone, we will not get the stair case (strictly increasing). In that case we can say it is not almost increasing strictly!
In case if that is not the case we can go on to search for another stone in our path. If we find another stone(n=2), then we do not have an option to move further. (since we can only remove one number!). So we are a super mario without life and have to confirm that the sequence is not almost increasing strictly.
In case we do not find any stone or only one stone (n=0 or 1), then we can climb till the end! So then the sequence is almost strictly increasing!
In this algorithm, the worst case is when it return True. Every element is compared with its successive elements and control flows out of the loop. So the algorithmic complexity will be O(n).
Comments
Post a Comment