How to find if an array is strictly in an increasing order after omitting only one element

Question

I have given the following problem where I am stuck right now. I am not having the perfect logic for this. Here is the problem below :

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.

Example 1:

For sequence = [1, 3, 2, 1], the output should be false. 
There is no one element that can be removed to get a strictly an increasing sequence

Example 2:

For sequence = [1, 3, 2], the output should be true.
You can remove 3 or 2 to get the strictly increasing sequence [1, 2] or [1,3] respectively

---

I have tried as follows :

boolean almostIncreasingSequence(int[] sequence) {
    ArrayList<Integer> list = new ArrayList<>();

    for(int i=0; i<sequence.length;i++) {
        list.add(sequence[i]);
    }

    int omittedCounter = 0;

    boolean status = true;

    for(int i=1; i<list.size();i++) {
        if(list.get(i-1) >= list.get(i)) {
            omittedCounter ++;
            list.remove(i-1);
            break;
        }
    }

    if (omittedCounter > 0) {
        for(int i=1; i<list.size();i++) {
            if(list.get(i-1) >= list.get(i)) {
                omittedCounter ++;
                list.remove(i-1);
                break;
            }
        }
    }

    if (omittedCounter > 1) {
        status = false;
    }

    return status;
}

But I am having trouble when I am given this sequence: [1, 2, 3, 4, 3, 6]

Output:           false
Expected Output:  true

Answer 1

This is possible in linear time O(n) and constant space O(1).

public static boolean analyse(int[] sequence) {
    if (sequence.length <= 2) return true;
    int a = sequence[0];
    int b = sequence[1];
    int drops = 0;
    if (a >= b) {
        drops++;
        a = b - 1; //drop a, keeping the smallest, fake a value for the first loop
    }
    // consider 3 items at a time, a, b & c
    for (int i = 2; i < sequence.length; i++) {
        int c = sequence[i];
        if (a < b && b < c) {
            // all good, move on
            a = b;
            b = c;
            continue;
        }
        // we'll have to drop one of them
        drops++;
        if (drops > 1) return false;
        // which one will we drop, b or c?
        if (a < c) {
            // drop b (a,b -> a,c)
            b = c;
        } // else drop c (a,b -> a,b)
    }
    return true;
}

Answer 2

One way to achieve that is doing something like this (approx. O(n*2) in worst scenario):

static boolean analyse(int[] sequence){
    int counter =0;
    //LinkedHashSet Keep Order But Remove Duplicates
    Set<Integer> set = new LinkedHashSet<>();
    //Copy Array To The Set
    for(int i=0; i<sequence.length; i++){
        set.add(sequence[i]);
    }
    //Count How Many Duplicates Found
    counter+=(sequence.length-set.size());

    if(counter>1){return false;}
    Integer[] seq = set.toArray(new Integer[set.size()]);

    // Loop Through The Array
    // If Any Breaks The Rule -> Increment Counter
    for(int i=0; i<seq.length-1; i++){
       if(i==0 && seq[i]>seq[i+1]) {counter++;}
       if(i!=0 && !(seq[i]<seq[i+1]&&seq[i-1]<seq[i])){counter++;}
       if(counter>1){return false;}
    }
    return true;
}

Test

int [] s  = {1,2,3,4,3,5};
int [] s1 = {1,2,3,4,3,6,1};
int [] s2 = {1,2,3,4,3,6};
int [] s3 = {1,2,3,10,10,6};
int [] s4 = {1,2,3,10,3,6};
System.out.println(analyse(s));
System.out.println(analyse(s1));
System.out.println(analyse(s2));
System.out.println(analyse(s3));
System.out.println(analyse(s4));

Output

true
false
true
false
false

Answer 3

I have one answer of it which have time complexity of N*Log(N). We will find out longest almost increasing sequence and check if it is equal to or greater than (N-1) , Then we will return true else false.

Checkout :

public int FindIndex(int A[], int l, int r, int key) {
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (A[m] >= key) r = m;
        else l = m;
    }
    return r;
}

public boolean LongestIncreasingSubsequenceLength(int A[], int size) 
{
    int[] Seq = new int[size];
    int len;
    Seq[0] = A[0];
    len = 1;
    for (int i = 1; i < size; i++) {
        if (A[i] < Seq[0]) Seq[0] = A[i];
        else if (A[i] > Seq[len - 1]) Seq[len++] = A[i];
        else Seq[FindIndex(Seq, -1, len - 1, A[i])] = A[i];
    }
    return len >= size - 1;
}

Answer 4

In Python3,

def almostIncreasingSequence(sequence): # checking whether there are more than one repeated element, this is to decrease complexity! As we need strictly increasing order after removal of one item, there cannot be more than one repeated item if only removing that is to give us the strictly increasing order. if len(sequence) - len(set(sequence)) > 1: return False # delete/pop one element from the both copies of list, sort one list and compare with the other copy to check whether both copies are equal for i, n in enumerate(sequence): temp = sequence.copy() temp2 = sequence.copy() temp.pop(i) temp2.pop(i) temp.sort() if temp == temp2: return True return False