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

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.

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.

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 

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).