(codefights) check for almost increasing subsequence

Question

(This problem is from CodeFights, so I'm not entirely sure that I should be posting a solution here, but given that some people posted a solution to this problem in the comments I think I should be OK.)

The input to the code is an array of integers, and an almost increasing sequence is such an array that can be turned into a strictly increasing sequence of integers by removing 0 or 1 elements. The output should be true if the array is an almost increasing sequence, and false otherwise.

boolean almostIncreasingSequence(int[] sequence) {
    boolean noFailuresYet = true;
    for(int i = 0; i < sequence.length-1; i++) {
        if(sequence[i] >= sequence[i+1]) {
            if(noFailuresYet) {
                if(i != 0 && i != sequence.length-2) {
                    if(sequence[i+1] <= sequence[i-1]) {
                        //Here we run the next iteration of the loop manually
                        //Alternatively we could set sequence[i] = sequence[i-1]
                        //but I don't want to modify the input array
                        //in case this function were to get used to check something elsewhere
                        if(sequence[i+2] <= sequence[i]) {
                            return false;
                        }
                        i++;
                    }
                }
                noFailuresYet = false;
            } else {
                return false;
            }
        }
    }
    return true;
    }

What I don't like about this code is that it has a bunch of nested if statements.

After looking at a solution code, I saw that the condition in the 2 innermost if statements could be replaced by a local check that returns false immediately if there is a certain local pattern, but I would like to know if I can reduce the nested if statements without using that (unless there is a natural way to come up with that idea by thinking about improving the code).

Answer 1

Break the problem into parts.

public static int findDecreasingElement(int[] sequence) {
    for (int i = 1; i < sequence.length; i++) {
        if (sequence[i - 1] >= sequence[i]) {
            return i;
        }
    }

    return sequence.length;
}

This is mostly a simpler version of your method. But it has a couple of differences:

If we change the i to start at 1, we don't need to subtract from sequence.length. And while we have to subtract from i, we don't need to add to i.

This returns the number of increasing elements that were found. Now we can

    int increasingCount = findDecreasingElement(sequence);
    if (increasingCount == sequence.length) {
        // the whole sequence is increasing
        return true;
    }

    // if increasingCount is 1, then we can't check index -1
    // but the desired relationship is true
    if (increasingCount == 1 || sequence[increasingCount - 2] < sequence[increasingCount]) {
        // the element at increasingCount - 1 is exceptionally big, so remove that
        return findDecreasingElement(sequence, increasingCount) == sequence.length;
    }

    if (sequence[increasingCount - 1] < sequence[increasingCount + 1]) {
        // The element at increasingCount is exceptionally small, so remove it
        return findDecreasingElement(sequence, increasingCount + 1) == sequence.length;
    }

    // neither removing at increasingCount - 1 nor increasingCount helps
    return false;

Now we have two simple problems. We find the longest strictly increasing sequence from the start. If that's the whole sequence, we're done. If not, we check to see if we can delete either of the offending elements. If we can, check if the remainder of the sequence is increasing.

To do that, we need a new method that is almost the same as our original method.

    public static int findDecreasingElement(int[] sequence, int start) {
        for (int i = start + 1; i < sequence.length; i++) {
            if (sequence[i - 1] >= sequence[i]) {
                return i;
            }
        }

        // if there are no decreasing elements, return the index of the end
        return sequence.length;
    }

And a helper method to replace our original method.

    public static int findDecreasingElement(int[] sequence) {
        return findDecreasingElement(sequence, 0);
    }

Now we have two method signatures but only one method doing the actual work.

These smaller methods are dead simple. Only one if and it's pretty clear why it needs to be there. No nesting at all.

The method that calls those methods has three if statements, but they aren't nested.

In terms of performance, this does the same linear scan as the original, just in two parts. It scans up to the first decreasing element, then it tries to scan the rest of the array. So except for those elements right around the decreasing element, it only scans each element twice (once to compare it to the previous element and once to compare it to the succeeding element).