Checking if a sequence is almost strictly increasing

Question

The question

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.

My java solution

boolean almostIncreasingSequence(int[] sequence) {

    Integer[] arr = new Integer[sequence.length];

    for(int ctr = 0; ctr < sequence.length; ctr++) {
        arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value
    }
    System.out.println("Integer :: " + arr);
    List<Integer> al = new ArrayList<Integer>(); 

    // adding elements of array to arrayList. 
    Collections.addAll(al, arr);
    System.out.println("list :: " + al);
    int save, flag = 0;
    for(int i=0; i<al.size(); i++) {
        save = al.get(i);
        al.remove(i);
        if(al.size()==1) return true;
        for(int j=0; j<al.size()-1; j++) {
            if(al.get(j+1) > al.get(j)) {
                flag = 0;
                continue;
            }
            else {
                flag = 1;
                break;
            }
        }
        if(flag == 0) {
            return true;
        }
        al.add(i,save);
    }

    if(flag == 1)
        return false;
    return true;
}

Here, I have created 2 for loops because in the first loop I'm generating the list where each index will be removed and in the second loop I'm iterating over the new list which has removed the element.

like sample array is {1,2,4,3} then in the first loop I'm creating an array which will be {2,4,3},{1,4,3},{1,2,3} and {1,2,4}. In the second loop I'm iterating over all these 4 arrays to compare each element.

The problem

For some of the test cases, it shows that it takes more than 3 seconds to execute this. But, I'm not sure where can I make a change to execute it faster. I don't have access to the test case.

Answer 1

You are repeating a lot of work.

For example, let's take a look at the sequence [1,2,3,4,5].

Your code does the following:
- copy it to a list
- remove "1" and check if {2,3,4,5} is sorted
- remove "2" and check if {1,3,4,5} is sorted
- remove "3" and check if {1,2,4,5} is sorted
- remove "4" and check if {1,2,3,5} is sorted
- remove "5" and check if {1,2,3,4} is sorted

Instead, let's go over the entire sequence once and do something special on the first item that is smaller than the previous one.

At some point into the loop we see the following where sequence[i-1] > sequence[i]

{done part, a, sequence[i-1], sequence[i], c, remainder}

The whole start of the sequence up to sequence[i-1] is strictly increasing (checked in earlier iterations of the loop). So what do we still need to check here to give a meaningful answer?

Given that sequence[i-1]>sequence[i] either one of those needs to be removed. So we have 2 cases:

• remove sequence[i-1] -> check if {a, sequence[i], c, remainder} is strictly increasing
• remove sequence[i] -> check if {a, sequence[i-1], c, remainder} is strictly increasing

Note that in both cases we want to check if the remainder is strictly ascending. So the main loop will look something like this:

for(int i = 1; i < sequence.length; i++){
    if (sequence[i - 1] > sequence[i]) {
        // {..., a, sequence[i-1], sequence[i], c, remainder}
        //check if remainder is sorted
        for(int j = i+1; j < sequence.length; j++){
            if (sequence[j - 1] > sequence[j]) {
                return false;
            }
        }
        int a = sequence[i - 2];
        int c = sequence[i + 1];
        //remove i-1
        if (a < sequence[i] && sequence[i] < c) {
            return true;
        }
        //remove i
        if (a < sequence[i - 1] && sequence[i - 1] < c) {
            return true;
        }
        //neither removing i-1 or i fixed the strictly increasing rule
        return false;
    }
}
//entire list is strictly increasing
return true;

There's still some edge cases that will cause trouble. This loop as it is now will throw an ArrayIndexOutOfBoundsException because we're accessing from sequence[i-2] up to sequence[i+1].

Let's handle those cases before the loop to keep things as simple as possible and reduce the bounds for the loop:

//trivial case with up to 2 items
if(sequence.length < 3){
    return true;
}
//edge case first 3 items are descending
if(sequence[0]>sequence[1]
        &&sequence[1]>sequence[2]) {
    return false;
}
//edge case last 3 items are descending
int last = sequence.length-1;
if(sequence[last-2]>sequence[last-1]
        &&sequence[last-1]>sequence[last]) {
    return false;
}
for(int i = 2; i < sequence.length-1; i++){ //skip first 2 and last item
    ...

With this we're no longer checking the same items over and over again and we no longer copy all the items into a list which should give you a major improvement in speed.

---

DISCLAIMER I have not tested this code. It's possible it contains typo's or other edge cases. Be sure to fully understand it instead of blindly copy-pasting.

Answer 2

I think your question only needs you to determine if there is more than one integer out of sequence in the array passed in.

You could just loop through the array passed in and if you find an integer out of sequence count it, then jump over it.

If you find a second integer out of sequence then return false, if you don't find another in the array then return true. You should be able to achieve this with one loop which will speed up your code..