Is there any way to make the execution faster in the below Java code?

Question

My Java code is as below.

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;
 }

The code is for a Problem "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."

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.

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.

• Arun Sudhakaran: right place would be codereview.stackexchange.com
• Roland Illig: Please let your editor or IDE format your code consistently. Currently it is harder to read than necessary.
• Prashant Zombade: Input array and expected result will help us in understanding the problem better.
• Hulk: Your current algorithm has a time complexity of O(N²), while this task is feasible in O(N). Andy's answer outlines one algorithm to do that.

Answer 1

The main observation is that the list can be decomposed into 3 (possibly empty) parts:

list = list[0..s) + list[s..e) + list[e..length)

Where list[0..s) and list[e..length) are strictly-increasing lists, and list[s..e) is the stuff in between.

Because you know that these prefix and suffix lists are strictly increasing, you don't need to check this property repeatedly within these lists.

You can pick any values for s and e subject to the constraint 0 <= s <= e < length, but assume that you pick them such that s is as big as possible, and e is as small as possible.

If the list has the desired overall property, then either:

• s == length, so the list is already strictly increasing without removing anything.
• list[s..e) has length at most 1 (e-s == 1), and list[0..s) + list[e..length) is strictly increasing. You can check this by simply comparing list[s-1] < list[e].
• list[s..e) is empty (s == e), and so you require either list[0..s-1) + list [e..length) (i.e. dropping the last element of the prefix) or list[0..s) + list[e+1..length) (i.e. dropping the first element of the suffix) to be strictly increasing. Check (s == 0 || list[s-1] < list[e]) and (e+1 == length || list[s] < list[e+1]) respectively.
• If list[s..e) has more than 1 element (e-s > 1), you would need to remove more than one element to give the list the desired property.

To find s and e:

Start with an integer pointer s at zero. Increment it until it reaches the end or it points to an element such that list[0..s) is a strictly increasing list, but list[0..s+1) would not be.

Start with an integer pointer e at the list's length. Decrement it while e>s and list[e-1..length) would not be a strictly increasing list.

• Roland Illig: How did you come up with that solution? Most probably the original poster is not interested in just having a solution but in finding it, so that would be good to explain.
• Torben: @RolandIllig Solutions like this are the result of creative thinking. When people say programming is a form of art they mean this. There's no algorithm to it. Experience helps.
• Andy Turner: @Torben I'd call it vocabulary or repertoire rather than creative thinking.
• Torben: @AndyTurner "Creative application of your vocabulary." :)

Answer 2

Your code contains 2 nested for loops, which both iterate through the whole list. This means that if your list has 100000 items, the code will need 100000*100000 steps, in the worst case. Of course this is slow.

Since the list is always "almost sorted", you probably don't need to inspect the beginning of the list since you already know it is sorted. Intuitively it should be enough to look at the last few list items and remember how many unsorted pairs the list contains.

Answer 3

updated 2: try this code also (in max 2 loops) Further optimization are posible but still produce O(n) time

public class TstList {
public static boolean compute(int a[]) {
 if (compute_1(a))
 return true;
 return compute_2(a);
}
public static boolean compute_1(int a[]) {
 if (a.length < 2)
 return true;
 int previous = a[0];
 int counter = 0;
 for (int i = 1; i < a.length; i++) {
 if (previous < a[i]) {
 previous = a[i];
 continue;
 } else {
 if (i == 1)
 previous = a[i];
 else
 previous = a[i - 1];
 counter++;
 }
 if (counter > 1)
 return false;
 }
 return true;
}
public static boolean compute_2(int a[]) {
 if (a.length < 2)
 return true;
 int previous = a[0];
 int counter = 0;
 for (int i = 1; i < a.length; i++) {
 if (previous < a[i]) {
 previous = a[i];
 continue;
 } else {
 previous = a[i];
 counter++;
 }
 if (counter > 1)
 return false;
 }
 return true;
}
public static void main(String arg[]) {
 System.out.println(compute(new int[] { 1, 2, 3, 4, 6 })); \1円
 System.out.println(compute(new int[] { 1, 2, 3, 1, 4, 6 })); \2円
 System.out.println(compute(new int[] { 1, 2, 1, 3, 1, 4, 6 })); \3円
 System.out.println(compute(new int[] { 1, 2, 3, 4, 6, 3 })); \4円
 System.out.println(compute(new int[] { 3, 2, 1 })); \5円
 System.out.println(compute(new int[] { 10, 1, 2, 3, 4, 5 })); \6円
 System.out.println(compute(new int[] { 1, 2, 5, 3, 5 })); \7円
}
}

output

true \1円
true \2円
false \3円
true \4円
false \5円 
true \6円
true \7円

• Robby Cornelissen: Close to the solution I had. You can optimize a little further though: 1) you can return true if a.length <= 2, instead of < 2; 2) you can break out of the loop once the counter hits 2.
• Virus: It failed for {10, 1, 2, 3, 4, 5}. It should return true but returns false.
• Traian GEICU: @Robby, true with optimization. Basically same idea.Thx.
• Virus: It failed for {1, 2, 5, 3, 5}. Expected true and got false
• Traian GEICU: @Virus, true again. Have fix but wondering if is still optimal

Answer 4

I would go with this.

Edit: Provided updated solution. It is fast, but readability is not good. I also included a main() class with some standard sequences I tested this code against. (In a format that it is easy for a tester verifying this to add any extra cases).

/**
 * Returns true if by removing maximum 1-entry the sequence can be strictly increasing.If not, it returns false. Doesn't check
 * if sequence is empty
 */
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing(final int[] sequence)
{
 boolean isFirstNonDecreasingSequence = true;
 final int length = sequence.length;
 int maxValue = sequence[0];
 for (int i = 1; i < length; i++)
 {
 if (sequence[i] <= maxValue)
 {
 if (isFirstNonDecreasingSequence == true)
 {
 if ((i + 1) < length) // check this is not the last element
 {
 if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
 {
 // [i-1] is a local peak. Remove [i-1]
 if (i > 1)
 {
 if (sequence[i] <= sequence[i - 2])
 {
 return false;
 }
 }
 maxValue = sequence[i];
 }
 // else { // [i] is a local pit. Remove [i]. maxValue is not updated. }
 isFirstNonDecreasingSequence = false;
 }
 }
 else
 {
 return false;
 }
 }
 else
 {
 maxValue = sequence[i];
 }
 }
 return true;
}
public static void main(final String[] args)
{
 final List<int[]> testInputs = new ArrayList<>();
 final List<Boolean> correctResults = new ArrayList<>();
 final List<Boolean> results = new ArrayList<>();
 testInputs.add(new int[] { 0 }); // single-element sequence
 correctResults.add(true);
 testInputs.add(new int[] { 0, 0 }); // two-element sequence
 correctResults.add(true);
 testInputs.add(new int[] { 0, 0, 0 }); // constant sequence
 correctResults.add(false);
 testInputs.add(new int[] { 1, 2, 3, 4, 6 }); // strictly increasing
 correctResults.add(true);
 testInputs.add(new int[] { 3, 2, 1 }); // strictly decreasing
 correctResults.add(false);
 testInputs.add(new int[] { 10, 1, 2, 3 }); // first value (10) should be removed
 correctResults.add(true);
 testInputs.add(new int[] { 1, 2, 3, 1 }); // last value (1) should be removed
 correctResults.add(true);
 testInputs.add(new int[] { 1, 2, 5, 3, 5 }); // peak (5) (inner value should be removed)
 correctResults.add(true);
 testInputs.add(new int[] { 1, 2, 3, 10, 4, 4, 5 }); // peak (10) followed by constant (4)
 correctResults.add(false);
 testInputs.add(new int[] { 1, 2, 3, 1, 4, 6 }); // pit (1) (inner value should be removed)
 correctResults.add(true);
 testInputs.add(new int[] { 5, 6, 2, 6, 7 }); // pit (2) that does not recover
 correctResults.add(false);
 testInputs.add(new int[] { 5, 0, 3 }); // first value should be removed
 correctResults.add(true);
 testInputs.add(new int[] { 5, 6, 1, 2 }); // sequence downward gap (pit)
 correctResults.add(false);
 for (int i = 0; i < testInputs.size(); i++)
 {
 results.add(checkIfRemovingMaxOneElementItIsStrictlyIncreasing_NoAssignment(testInputs.get(i)));
 if (correctResults.get(i) == results.get(i))
 {
 System.out.println("Test case: " + i + " successful.");
 }
 else
 {
 System.out.println("Test case: " + i + " should be: " + correctResults.get(i) + " but was: " + results.get(i));
 System.out.println("Test case: " + i + " input array: " + Arrays.toString(testInputs.get(i)));
 }
 }
}

Furthermore, if you don't care if a specific value is destroyed, you can avoid the extra variable:

private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing_WithoutAssignment(final int[] sequence)
{
 boolean isFirstNonDecreasingSequence = true;
 final int length = sequence.length;
 for (int i = 1; i < length; i++)
 {
 if (sequence[i] <= sequence[i - 1])
 {
 if (isFirstNonDecreasingSequence == true)
 {
 if ((i + 1) < length) // check this is not the last element
 {
 if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
 {
 // [i-1] is a local peak. Remove [i-1]
 if (i > 1)
 {
 // Check if by removing [i-1] the sequence is actually increasing
 if (sequence[i] <= sequence[i - 2])
 {
 return false;
 }
 }
 }
 else
 {
 // [i] is a local pit. Remove [i]
 sequence[i] = sequence[i - 1];
 }
 isFirstNonDecreasingSequence = false;
 }
 }
 else
 {
 return false;
 }
 }
 }
 return true;
}

In both versions there are a lot of ifs inside the code. That's true, but they will only be executed the first time that the sequence detects a non-increasing sequence of two consecutive values. So performance-wise this should be okay.

As to the logic:
When it detects that at the index [i]: A[i-1]>=A[i], it determines whether its after a peak (thus A[i-1] is "abnormally" high and should be removed from the sequence) or it is inside a pit (the A[i] is too low and should be removed from the sequence).

• Virus: It failed for {1, 2, 1, 2} Expected false but got true.
• talex: [10, 11, 12, 1, 2, 3] will return true but should false
• tryman: @Talex, you are right. The updated proposal passes this test. Virus, yes, I misread "increasing" where you said "strictly increasing", by using <= instead of < the test was successful. In any case, I proposed an alternative solution since that previous one failed in other cases as well.
• tryman: @Virus Did you ever test it? If yes, how was the performance improvement for your task?