Checking if sequence is almost strictly in ascending order

Question

This was part of my interview questions.

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

For instance,

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

We can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, we can remove 2 to get the strictly increasing sequence [1, 3].

The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

The conceptual algorithm that the interviewer wanted was below with Java:

boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

but I didn't get the part comparing sequence[i] with sequence[i+1] andsequence[i+2] to increment the counter which are seq1 and seq2. How does this cover all the cases?

Answer 1

It does not cover all cases! Consider the sequence [2, 6, 4, 8, 7]. Before the return statement, the values of seq1 and seq2 are: $seq_1 = 2$, $seq_2 = 0$. So the function would return $True$. However, the sequence is not almost strictly increasing, because you need to remove at least two elements from it to obtain an increasing sequence.

So, either the Java implementation is not faithful to the conceptual algorithm, or the conceptual algorithm is wrong.

The problem can be solved by finding the length of the longest increasing subsequence (LIS) of the given sequence. Call $n$ the length of the original sequence. If the LIS has length $\ge n-1$, the sequence is almost increasing according to your definition. If the LIS has length $\le n-2$, the sequence is not almost increasing.

Answer 2

Indeed the method almostIncreasingSequence does not cover all the cases. So there must be something wrong about the interview.

Here is the simplest counterexample, [2,1,4,3]. Because 2,1 and 4,3 are two disjoint decreasing pairs, we need to remove at least two elements to change it into a strictly increasing sequence. That array is not an almost strictly increasing sequence. However, almostIncreasingSequence will return true.

The answer by Vincenzo suggests that longest increasing subsequence can be used to solve this problem. While that algorithm can do the job, it is not easy to implement and it runs in $O(n\log n)$ time-complexity, where $n$ is the length of the given sequence.

Here is a simple correct method that runs in $O(n)$. The idea is simple. Once we find an adjacent pair of elements that is not strictly increasing, we check if we can remove one of them so that nearby elements become strictly increasing. If not, then we return false. If yes, then we will check the remaining elements. A standard padding trick is used so that we can check the boundary cases and the ordinary cases uniformly.

boolean isAlmostIncreasingSequence(int[] sequence) {
    // Pad the sequence so that we can reason with less cases.
    int[] padded = new int[sequence.length + 2];
    padded[0] = Integer.MIN_VALUE;
    padded[padded.length - 1] = Integer.MAX_VALUE;
    System.arraycopy(sequence, 0, padded, 1, sequence.length);

    int bad = -1;

    // find the first not strictly increasing pair
    for (int i = 1; i < padded.length - 1; i++) {
        if (padded[i] >= padded[i + 1]) {
            bad = i;
            break;
        }
    }

    if (bad != -1) {
        // Can we succeed if we remove the element at bad or bad+1?
        if (padded[bad - 1] < padded[bad + 1] && padded[bad + 1] < padded[bad + 2]
                || padded[bad] < padded[bad + 2]) {
            // all the rest of the padded sequence
            for (int i = bad + 2; i < padded.length - 1; i++) {
                if (padded[i] >= padded[i + 1]) {
                    return false;
                }
            }
        } else {
            return false;
        }
    }

    return true;
}

Answer 3

You scan until you find the first two elements that are not in strictly ascending order (in your example 3 is not less than 2). One of them must be removed.

Assume a [i] ≥ a [i+1]. If i > 0 and a [i+1] ≤ a [i-1] then you cannot remove a [i], so you have to remove a[i+1]. In all other cases you would remove a[i].

Then you check that with this item removed, the rest is in strictly ascending order. If you find another item in the wrong order, you return "false".

Answer 4

Strictly ascending requires not to have repeated values after removing one element from the array. Hence there should never be more than one repeated element.

In Python3, def almostIncreasingSequence(sequence): # To check if there are more than one repeated numbers, set() can be used to eliminate repetitions # len(x) to find the count of array x # len(set(x)) - remove repetition and find count if len(sequence) - len(set(sequence)) > 1: return False # popping each element and checking whether the remaining array is same # as the original after sorting one of the copy for i, n in enumerate(sequence): # list.copy() to make a copy of the array temp = sequence.copy() temp2 = sequence.copy() #list.pop(i) to delete the element at index i temp.pop(i) temp2.pop(i) # list.sort() to sort array in ascending order temp.sort() if temp == temp2 and (len(temp) - len(set(temp))) == 0: return True return False