2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think what they were trying to do was: if there's at most one index i for which a[i] > a[i+1] and for that index a[i-1] < a[i+1] (or i == 0). That's not what the algorithm does, though. $\endgroup$ – Raphael Nov 18 '18 at 11:29
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.