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.