Is there any way of an infinite loop here?

[Sergiu Dobozi]

So I was on Code Fights recently and I am barely on level 2 in Java. Here is a task I have recently stumbled on.
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

   For sequence = [1, 3, 2, 1], the output should be
   almostIncreasingSequence(sequence) = false;

   There is no one element in this array that can be removed in order to get a strictly increasing sequence.

   For sequence = [1, 3, 2], the output should be
   almostIncreasingSequence(sequence) = true.

   You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
The code I wrote works for all cases except for one:

boolean almostIncreasingSequence(int[] sequence) {
 int[] sequence2 = new int[sequence.length - 1];
 for (int c = 0; c < sequence.length; c++) {
  for (int i = 0, j = 0; i < sequence2.length; i++, j++) {
   if (c==i) {
    j++;
    sequence2[i] = sequence[j];
   } else
    sequence2[i] = sequence[j];
   
  }
if (isSorted(sequence2))
    return true;
 }
 
 return false;
}

public static boolean isSorted(int[] a) {
 for (int i = 0; i < a.length - 1; i++) {
  if (a[i] >= a[i + 1]) {
   return false;
  }
 }
 return true;
}

The non-working case is a hidden case so I have no idea what case where I would have an infinite loop. Can you see the reason for such an error?

[Liutauras Vilda]

Sergiu Dobozi wrote:The non-working case is a hidden case so I have no idea what case where I would have an infinite loop.

So, you say the problem is that on some inputs you'd run into infinite (non ending) program?

I see problem if sequence is either empty or null, so you don't check for those, but these cases wouldn't cause anything infinite. Please clarify or better copy paste exact text from where you take this challenge.

[Junilu Lacar]

Why do you assume it's an infinite loop that's the problem? Any An array with less than three elements and non-increasingly ordered values will fail a test because it will result in your sorted() method returning true. I doubt that a zero- or one-element array should be considered as an increasing sequence. To tell if you have a strictly increasing sequence, you need at least two elements, don't you?

I think it's your sorted method that's the problem.

[Junilu Lacar]

Take for example the sequence [3, 1] : can you take away at most one element to get strictly increasing sequence? Assuming a strictly increasing sequence has to have at least 2 elements, then you can't, so this should return false. Your program, however, will return true.

[Sergiu Dobozi]

Junilu Lacar wrote:Why do you assume it's an infinite loop that's the problem? Any array with less than three elements will probably fail a test because it will result in your sorted() method returning true. I doubt that a zero- or one-element array should be considered as an increasing sequence. To tell if you have a strictly increasing sequence, you need at least two elements, don't you?

I think it's your sorted method that's the problem.

This is what Code Fights gives me as an error:
"Execution time limit exceeded on test 26: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input."

So I assumed that it is referring to an infinite loop.

[Liutauras Vilda]

Alright, so problem is different.

What you do, lets say on input {1, 2, 7, 4, 0, 5, 6, ... N-1}. You copy whole array and then checking if it's sorted. But you know right away after 2, 7, 4, ... 0... that this combination can't be sorted, but you still going to copy the rest of the elements.

[Junilu Lacar]

Probably a more difficult challenge is to come up with a recursive solution that doesn't use explicit iteration, just array slices. I know that array slices are a somewhat foreign term for most Java programmers and there's no native language support for them but you can write a utility class and use java.util.Arrays to get them.

[Liutauras Vilda]

And i'm not sure why you need to do all that copying. You can I think just check previous element if it is smaller. Then advance counter, and again...

[Liutauras Vilda]

Thinking a bit in a rush now, but i think you just need to find first element which is smaller than previous, then skip that and check if the rest elements are greater than the one before you skipped, and that is it I think.

[edit] hm.. that might won't work in some cases.. don't know about that now

[Junilu Lacar]

Liutauras is correct about long arrays.  I tried with 50K numbers and it took a few seconds to complete on my Mac. This code will eventually fail for long arrays, depending on how impatient the test harness is.

[Sergiu Dobozi]

Liutauras Vilda wrote:Thinking a bit in a rush now, but i think you just need to find first element which is smaller than previous, then skip that and check if the rest elements are greater than the one before you skipped, and that is it I think.

[edit] hm.. that might won't work in some cases.. don't know about that now

This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
This is my implementation:

boolean almostIncreasingSequence(int[] sequence) {

  for (int i = 0; i < sequence.length-2; i++) {
   if (sequence[i] >= sequence[i+1]) 
   {if(sequence[i] >= sequence[i+2])
 
    return false;
   }
  }
 
 return true;
}

[Sergiu Dobozi]

Junilu Lacar wrote:Liutauras is correct about long arrays.  I tried with 50K numbers and it took a few seconds to complete on my Mac. This code will eventually fail for long arrays, depending on how impatient the test harness is.

Thank you for testing it. I'm at work so I don't have access to any programming software.
Now I know that at least there was no logical problem.

[Piet Souris]

Well, it is not an infinite loop, but OP'current implementation will have a solution time that is very dependent on the array in question.
As Junilu writes, if an array is already sorted, then the progrram will terminate very quickly, since the first attempt will be succesfull, However, with an average array, run time will go up dramatically. For instance try:

public static void main(String... args) {
        int max = 1_000_000;
        Random r = new Random();
//        int[] arr = r.ints(1_000_000).toArray();
        int[] arr = IntStream.rangeClosed(1, max).toArray();
        System.out.println(almostIncreasingSequence(arr));
    }

This will very quickly end. But when running with the outcommented line will probably get you the time exceeds error.

Another way, find the two biggest elements and write down their indices. Now, if these indices are the two highest indices (array.length - 1 and array.length - 2), then what can you conclude? And what if these indices are not the highest two indices? That will give you a O(N) solution, if I'm not mistaken (which has a positive probability...)

Edit: well, the above is not correct, but it is in the right direction...

[Liutauras Vilda]

Sergiu Dobozi wrote:This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

That's not true.

Let me rephrase all that from a different end, I might wasn't clear enough. Find first element which is equal greater than next, skip that element, record that you removed/skipped one already, if that happens again, return false, otherwise true.

[Liutauras Vilda]

Piet Souris wrote:Another way, find the two biggest elements and write down their indices..And what if these indices are not the highest two indices?..That will give you a O(N) solution

So, at best it is O(N), mine described algorithm above at worst O(N).

[Dave Tolls]

Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

But it's a start point.

There are two situations, both of which can be initially spotted using Liutauras' suggestion.

10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.

and your example
1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.

That should be a pretty simple check.

So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.

There's probably other issues, but it's a start.

[Sergiu Dobozi]

Dave Tolls wrote:

Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

But it's a start point.

There are two situations, both of which can be initially spotted using Liutauras' suggestion.

10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.

and your example
1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.

That should be a pretty simple check.

So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.

There's probably other issues, but it's a start.

I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[-1]. So is this method really possible to implement?

[Junilu Lacar]

I wrote a 1-pass fail-fast loop and got decent performance. I tested with an int[Integer.MAX_VALUE / 8] and (seemingly) still got sub-second time to complete.

I used ChronoUnits and LocalDateTime so I might not be doing it right but I don't see much delay on the console.

    public static void main(String[] args) {
        assertEquals(true, almostSequential(1, 2));
        assertEquals(true, almostSequential(1, 2, 3, 4));
        assertEquals(true, almostSequential(100, 1, 2));
        assertEquals(true, almostSequential(1, 100, 2));
        assertEquals(true, almostSequential(longSeqArray(Integer.MAX_VALUE / 8)));

        assertEquals(false, almostSequential(1, 2, 4, 100, 4));
        assertEquals(false, almostSequential(1));
        assertEquals(false, almostSequential(2, 1));
        assertEquals(false, almostSequential(3, 2, 1));
        assertEquals(false, almostSequential(1, 5, 2, 7, 4, 5));
        assertEquals(false, almostSequential(longArray(5000000)));
    }

    private static int[] longSeqArray(int len) {
        int[] a = new int[len];
        for (int i = 1; i < len; i++) {
            a[i] = i;
        }
        return a;
    }

    private static int[] longArray(int len) {
        int[] a = new int[len];
        Random rand = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt();
        }
        return a;
    }

    static void assertEquals(boolean expected, boolean actual) {
        System.out.println(!(expected ^ actual) ? "Pass" : "Fail");
    }

    private static void reportTimeElapsed(LocalDateTime start, LocalDateTime end) {
        long secs = ChronoUnit.SECONDS.between(start, end);
        long millis = ChronoUnit.MILLIS.between(start, end);
        System.out.printf("%d secs %d millis %n", secs, millis - secs * 1000);
    }

and here's my output:

0 secs 52 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 197 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass

I suppose the first test always takes a hit for loading and other kinds of startup overhead. The 197 millis was for the Integer.MAX_VALUE / 8 long array of sequential numbers.  Couldn't use the max because I was running out of memory for the array.

[Junilu Lacar]

Basically, my algorithm counted drops, i.e., when arr[i] >= arr[i+1].  If you count more than 1 drop, then there is no need to proceed further.  Of course, when you find a drop, you have to check if dropping the high number will still result in a drop from the previous element. There are a couple of special cases that I checked up front, then I went into the general case that was covered by the fail-fast loop, which is only 7 lines of executable code, 10 lines if you count the lines with closing braces.  The almostSequential() method I wrote is about 12 lines of executable code, 20 lines with whitespace and full bracing.

[Junilu Lacar]

Sergiu Dobozi wrote:This is my implementation:

boolean almostIncreasingSequence(int[] sequence) {

  for (int i = 0; i < sequence.length-2; i++) {
   if (sequence[i] >= sequence[i+1]) 
   {if(sequence[i] >= sequence[i+2])
 
    return false;
   }
  }
 
 return true;
}

[100, 1, 2]
**Fail**

[1, 2, 4, 100, 4]
**Fail**

[1]
**Fail**

[2, 1]
**Fail**

[Dave Tolls]

Sergiu Dobozi wrote:
I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[-1]. So is this method really possible to implement?

Others may work differently, but I always suggest getting the basics down first (Junilu's tests are good for that).
Handle the edge cases once you've handled the general case.
In my opinion, trying to write something outright that covers all cases tends to result in you writing nothing.

[Junilu Lacar]

Dave Tolls wrote:I always suggest getting the basics down first (Junilu's tests are good for that). Handle the edge cases once you've handled the general case.

Minds that think alike...

Ironically, I missed one test case that you pointed out, Dave: [10, 20, 30, 40, 20, 50]

Sure enough, when I ran it, my implementation failed. It actually took me a while to figure out how to cover this one but with some refactoring to clarify intent, the code eventually pointed me to the right solution. I found a very good example of how too many implementation details can make it difficult to catch and eradicate a bug.    I will share my solution once we see one from OP that passes all the tests I wrote.

[Carey Brown]

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.

What is meant by "strictly"? (I'm assuming I can ignore this.)

Does each number have to be 1 more than the one before it? (assume: no)

Does the interval between successive pairs have to be the same? (assume: no)

Is a single number, e.g. [1], a "sequence"? (assume: no)

Test cases that should return true

[1, 2]
[1, 2, 3, 4]
[1, 3, 2]
[100, 1, 2, 3]
[1, 100, 2, 3]
[1, 2, 100, 3]
[1, 2, 3, 100]
[1, 200, 300, 2]
[100, 200, 300, 4]
[1, 200, 3, 400]
[1, 2, 3, 4]
[100, 200, 300, 400]
[1, 2, 4, 100, 4] // I disagree w/ Junilu on this one, I'd drop the last '4'

Test cases that should return false

null
[]
[1]
[2, 1]
[1, 3, 2, 1]
[1, 5, 2, 7, 4, 5]

I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.

[Junilu Lacar]

Carey Brown wrote:

What is meant by "strictly"? (I'm assuming I can ignore this.)

Does each number have to be 1 more than the one before it? (assume: no)

I think the second is what defines "strictly", that is, each number must be at least one more than the previous one, if there is one. "Non-strictly" speaking, you'd allow repeats of the same number.

Does the interval between successive pairs have to be the same? (assume: no)

Is a single number, e.g. [1], a "sequence"? (assume: no)

I made the same assumptions.

[1, 2, 4, 100, 4] // I disagree w/ Junilu on this one, I'd drop the last '4'[/code]
I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.

You're correct to disagree with me on this one. I do, too. That was a mistake and it's a faulty test because it has another solution than the one being tested. I actually spent literally 30 minutes refactoring my code to clarify intent before I realized this. I should have read your post earlier; I could have saved myself the frustration.

[Junilu Lacar]

Here's my cleaned up test harness. It would have been easier to write a JUnit test but I was on a roll so I just kept going with it...  

import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.Arrays;
import java.util.Random;

/**
 * Created by jlacar on 3/3/17.
 */
public class Sequence {

    private static Analyzer analyzer;
    private static int testCount;
    private static int passCount;

    private static int[] longSequence = longSeqArray(Integer.MAX_VALUE / 8);

    public static void main(String[] args) {
        runTests(new OpAlgorithm());
        runTests(new LiutaurasAlgorithm());
        runTests(new JuniluAlgorithm());
    }

    private static void runTests(Analyzer algorithm) {

        analyzer = algorithm;
        System.out.printf("Running %s%n", algorithm.getClass().getSimpleName());

        resetStats();

        runValidSequenceTests();
        runInvalidSequenceTests();
        runPerformanceRelatedTests();

        showStats();
    }

    private static void runValidSequenceTests() {
        smallestValid();

        dropHigherNumber();
        dropLowerNumber();
        dropRepeatedNumber();
    }

    private static void runInvalidSequenceTests() {
        cantDropHigherNumber();
        cantDropLowerNumber();

        sizeEdgeCases();

        tooManyOutOfSequence();
        tooManyRepeats();
    }

    private static void tooManyOutOfSequence() {
        display("Too many elements out of sequence from start",
                false, 10, 2, 10, 3, 4, 5, 6);

        display("Too many elements out of sequence in middle",
                false, 10, 20, 1, 30, 1, 40, 50, 60);

        display("Too many elements out of sequence at end",
                false, 10, 20, 30, 40, 50, 1, 60, 1);
    }

    private static void sizeEdgeCases() {
        display("Not enough elements",
                false, 1);

        display("Smallest one that will fail",
                false, 2, 1);

        display("Longer one that will fail",
                false, 4, 3, 2, 1);
    }

    private static void cantDropLowerNumber() {
        display("Drop low number in middle but repeated number in middle",
                false, 10, 20, 30, 1, 30, 40, 50);

        display("Drop low number in middle but repeated number at end",
                false, 10, 20, 30, 1, 30);
    }

    private static void cantDropHigherNumber() {
        display("Drop high number in middle but repeated number at start",
                false, 1, 100, 1, 2, 3);

        display("Drop high number in middle but repeated number in middle",
                false, 1, 2, 100, 2, 3);

        // INVALID TEST !!!
//        display("Drop high number in middle but repeated number at end",
//        false, 1, 2, 3, 100, 3);

        display("Drop high number in middle but still not increasing sequence",
                false, 2, 4, 6, 3, 5, 7);
    }

    private static void tooManyRepeats() {
        display("Too many repeats at start",
                false, 1, 1, 1, 10, 20);

        display("Too many repeats in middle",
                false, 1, 2, 3, 3, 3, 4, 5);

        display("Too many repeats at end",
                false, 1, 2, 3, 4, 5, 5, 5);
    }

    private static void runPerformanceRelatedTests() {
        int big = 1_000_000;
        int[] failFast = longSeqArray(big);

        // set up first drop
        failFast[3] -= 2;

        // set up second drop
        failFast[6] -= 2;

        display(String.format("Fail fast with two drops at front of long (%,d elements) array", failFast.length),
                false, failFast);

        // time complexity

        // revert second drop, set up another drop at the end
        failFast[6] += 2;
        failFast[big - 2] -= 2;

        display("Second drop at end of long sequence",
                false, failFast);

        display(String.format("Time to traverse a long (%,d elements) sorted array", longSequence.length),
                true, longSequence);
    }

    private static void dropRepeatedNumber() {
        display("Drop repeated number, first element",
                true, 1, 1, 20, 30);

        display("Drop repeated number, middle element",
                true, 1, 2, 2, 3);

        display("Drop repeated number, last element",
                true, 1, 2, 30, 30);
    }

    private static void dropLowerNumber() {
        display("Drop low number, middle element",
                true, 10, 20, 30, 2, 40, 50);

        display("Drop low number, last element",
                true, 10, 20, 30, 2);
    }

    private static void dropHigherNumber() {
        display("Drop high number, first element",
                true, 30, 1, 2);

        display("Drop high number, middle element",
                true, 1, 30, 2);
    }

    private static void smallestValid() {
        display("Smallest one that will pass",
                true, 1, 2);
    }

    private static void display(String description, boolean expected, int... sequence) {
        System.out.printf("%n%s: ", description);

        if (sequence.length < 10) {
            System.out.println(Arrays.toString(sequence));
        } else {
            System.out.println(Arrays.toString(Arrays.copyOfRange(sequence, 0, 12)));
        }

        almostSequential(expected, sequence);
    }

    private static int[] longSeqArray(int len) {
        int[] a = new int[len];
        for (int i = 1; i < len; i++) {
            a[i] = i;
        }
        return a;
    }

    private static int[] longArray(int len) {
        int[] a = new int[len];
        Random rand = new Random(2000);
        for (int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt(len);
        }
        return a;
    }

    private static void almostSequential(boolean expected, int... sequence) {
        LocalDateTime start = LocalDateTime.now();
        boolean actual = analyzer.almostSequential(sequence);
        processResult(actual == expected, start, LocalDateTime.now());
    }

    private static void processResult(boolean passed, LocalDateTime start, LocalDateTime end) {
        updateStats(passed);

        long secs = ChronoUnit.SECONDS.between(start, end);
        long millis = ChronoUnit.MILLIS.between(start, end);
        System.out.printf("%s (%d secs %d millis)%n", passed ? "Passed" : "**Failed**", secs, millis - secs * 1000);
    }

    private static void showStats() {
        System.out.printf("%n%d of %d tests passed%n%n", passCount, assertCount);
    }

    private static void resetStats() {
        passCount = 0;
        testCount = 0;
    }

    private static void updateStats(boolean passed) {
        testCount++;
        if (passed) passCount++;
    }

}

abstract class Analyzer {
    public abstract boolean almostSequential(int... sequence);
}

class JuniluAlgorithm extends Analyzer {

    @Override
    public boolean almostSequential(int... sequence) {
        // will share when OP has a solution that passes all tests
    }

    // ... a bunch of extracted helper methods
}

class LiutaurasAlgorithm extends Analyzer {

    @Override
    public boolean almostSequential(int... a) {
        boolean secondChanceAllowed = true;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] >= a[i + 1] && secondChanceAllowed) {
                secondChanceAllowed = false;
                continue;
            }
            if (a[i] >= a[i + 1] && !secondChanceAllowed) {
                return false;
            }
        }
        return true;
    }
}

class OpAlgorithm extends Analyzer {

    @Override
    public boolean almostSequential(int... sequence) {
        for (int i = 0; i < sequence.length - 2; i++) {
            if (sequence[i] >= sequence[i + 1]) {
                if (sequence[i] >= sequence[i + 2])
                    return false;
            }
        }
        return true;
    }
}

[Carey Brown]

LiutaurasAlgorithm -----------------------------------------
*FAIL*  true   sec: 0.000  [10, 20, 30, 5, 6]

[Carey Brown]

OK Junilu, I concede. Changed my algorithm and swapped those specific true/false cases.
New output:

CareyAlgorithm -----------------------------------------
 PASS   true   sec: 0.000  [1, 2]
 PASS   true   sec: 0.000  [1, 2, 3, 4]
 PASS   true   sec: 0.000  [1, 3, 2]
 PASS   true   sec: 0.000  [100, 1, 2, 3]
 PASS   true   sec: 0.000  [1, 100, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 100, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 100]
 PASS   true   sec: 0.000  [1, 200, 300, 2]
 PASS   true   sec: 0.000  [100, 200, 300, 4]
 PASS   true   sec: 0.000  [1, 200, 3, 400]
 PASS   true   sec: 0.000  [100, 200, 300, 400]
 PASS   true   sec: 0.000  [1, 2, 4, 100, 4]
 PASS   true   sec: 0.000  [1, 2, 100, 3, 4, 5, 6, 200]
 PASS   true   sec: 0.000  [1, 1, 20, 30]
 PASS   true   sec: 0.000  [1, 2, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 3]
 PASS   false  sec: 0.000  []
 PASS   false  sec: 0.000  [1]
 PASS   false  sec: 0.000  [2, 1]
 PASS   false  sec: 0.000  [1, 1]
 PASS   false  sec: 0.000  [1, 3, 2, 1]
 PASS   false  sec: 0.000  [1, 5, 2, 7, 4, 5]
 PASS   false  sec: 0.000  [1, 5, 2, 3, 4, 9, 5, 6, 7]
 PASS   false  sec: 0.000  [100, 1, 2, 3, 4, 200, 5, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 2]
 PASS   false  sec: 0.000  [10, 20, 30, 5, 6]
 PASS   false  sec: 0.000  [1, 1, 1, 10, 20]
 PASS   false  sec: 0.000  [1, 2, 3, 3, 3, 4, 5]
 PASS   false  sec: 0.000  [1, 2, 3, 4, 5, 5, 5]
 PASS   false  sec: 0.000  [10, 20, 30, 1, 30]
 PASS   false  sec: 0.000  [4, 3, 2, 1]
JuniluAlgorithm -----------------------------------------
 PASS   true   sec: 0.000  [1, 2]
 PASS   true   sec: 0.000  [1, 2, 3, 4]
 PASS   true   sec: 0.000  [1, 3, 2]
 PASS   true   sec: 0.000  [100, 1, 2, 3]
 PASS   true   sec: 0.000  [1, 100, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 100, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 100]
 PASS   true   sec: 0.000  [1, 200, 300, 2]
 PASS   true   sec: 0.000  [100, 200, 300, 4]
 PASS   true   sec: 0.000  [1, 200, 3, 400]
 PASS   true   sec: 0.000  [100, 200, 300, 400]
 PASS   true   sec: 0.000  [1, 2, 4, 100, 4]
 PASS   true   sec: 0.000  [1, 2, 100, 3, 4, 5, 6, 200]
 PASS   true   sec: 0.000  [1, 1, 20, 30]
 PASS   true   sec: 0.000  [1, 2, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 3]
 PASS   false  sec: 0.000  []
 PASS   false  sec: 0.000  [1]
 PASS   false  sec: 0.000  [2, 1]
 PASS   false  sec: 0.000  [1, 1]
 PASS   false  sec: 0.000  [1, 3, 2, 1]
 PASS   false  sec: 0.000  [1, 5, 2, 7, 4, 5]
 PASS   false  sec: 0.000  [1, 5, 2, 3, 4, 9, 5, 6, 7]
 PASS   false  sec: 0.000  [100, 1, 2, 3, 4, 200, 5, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 2]
 PASS   false  sec: 0.000  [10, 20, 30, 5, 6]
 PASS   false  sec: 0.000  [1, 1, 1, 10, 20]
 PASS   false  sec: 0.000  [1, 2, 3, 3, 3, 4, 5]
 PASS   false  sec: 0.000  [1, 2, 3, 4, 5, 5, 5]
 PASS   false  sec: 0.000  [10, 20, 30, 1, 30]
 PASS   false  sec: 0.000  [4, 3, 2, 1]
LiutaurasAlgorithm -----------------------------------------
 PASS   true   sec: 0.000  [1, 2]
 PASS   true   sec: 0.000  [1, 2, 3, 4]
 PASS   true   sec: 0.000  [1, 3, 2]
 PASS   true   sec: 0.000  [100, 1, 2, 3]
 PASS   true   sec: 0.000  [1, 100, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 100, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 100]
 PASS   true   sec: 0.000  [1, 200, 300, 2]
 PASS   true   sec: 0.000  [100, 200, 300, 4]
 PASS   true   sec: 0.000  [1, 200, 3, 400]
 PASS   true   sec: 0.000  [100, 200, 300, 400]
 PASS   true   sec: 0.000  [1, 2, 4, 100, 4]
 PASS   true   sec: 0.000  [1, 2, 100, 3, 4, 5, 6, 200]
 PASS   true   sec: 0.000  [1, 1, 20, 30]
 PASS   true   sec: 0.000  [1, 2, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 3]
*FAIL*  true   sec: 0.000  []
*FAIL*  true   sec: 0.000  [1]
*FAIL*  true   sec: 0.000  [2, 1]
*FAIL*  true   sec: 0.000  [1, 1]
 PASS   false  sec: 0.000  [1, 3, 2, 1]
 PASS   false  sec: 0.000  [1, 5, 2, 7, 4, 5]
 PASS   false  sec: 0.000  [1, 5, 2, 3, 4, 9, 5, 6, 7]
 PASS   false  sec: 0.000  [100, 1, 2, 3, 4, 200, 5, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 2]
*FAIL*  true   sec: 0.000  [10, 20, 30, 5, 6]
 PASS   false  sec: 0.000  [1, 1, 1, 10, 20]
 PASS   false  sec: 0.000  [1, 2, 3, 3, 3, 4, 5]
 PASS   false  sec: 0.000  [1, 2, 3, 4, 5, 5, 5]
*FAIL*  true   sec: 0.000  [10, 20, 30, 1, 30]
 PASS   false  sec: 0.000  [4, 3, 2, 1]
OpAlgorithm -----------------------------------------
 PASS   true   sec: 0.000  [1, 2]
 PASS   true   sec: 0.000  [1, 2, 3, 4]
 PASS   true   sec: 0.000  [1, 3, 2]
*FAIL*  false  sec: 0.000  [100, 1, 2, 3]
*FAIL*  false  sec: 0.000  [1, 100, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 100, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 100]
 PASS   true   sec: 0.000  [1, 200, 300, 2]
 PASS   true   sec: 0.000  [100, 200, 300, 4]
 PASS   true   sec: 0.000  [1, 200, 3, 400]
 PASS   true   sec: 0.000  [100, 200, 300, 400]
 PASS   true   sec: 0.000  [1, 2, 4, 100, 4]
*FAIL*  false  sec: 0.000  [1, 2, 100, 3, 4, 5, 6, 200]
 PASS   true   sec: 0.000  [1, 1, 20, 30]
 PASS   true   sec: 0.000  [1, 2, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 3]
*FAIL*  true   sec: 0.000  []
*FAIL*  true   sec: 0.000  [1]
*FAIL*  true   sec: 0.000  [2, 1]
*FAIL*  true   sec: 0.000  [1, 1]
 PASS   false  sec: 0.000  [1, 3, 2, 1]
 PASS   false  sec: 0.000  [1, 5, 2, 7, 4, 5]
 PASS   false  sec: 0.000  [1, 5, 2, 3, 4, 9, 5, 6, 7]
 PASS   false  sec: 0.000  [100, 1, 2, 3, 4, 200, 5, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 2]
 PASS   false  sec: 0.000  [10, 20, 30, 5, 6]
 PASS   false  sec: 0.000  [1, 1, 1, 10, 20]
 PASS   false  sec: 0.000  [1, 2, 3, 3, 3, 4, 5]
 PASS   false  sec: 0.000  [1, 2, 3, 4, 5, 5, 5]
 PASS   false  sec: 0.000  [10, 20, 30, 1, 30]
 PASS   false  sec: 0.000  [4, 3, 2, 1]

[Carey Brown]

There's been an offline discussion on whether [], [1], [1,1], or [2,1] should result in a false outcome, and I guess I'm throwing my hat in with Junilu to say that these are false, meaning that after potentially dropping an element the results no longer represent a "sequence".

Here's the test cases that have come up so far:

		int[][] testTrue =
			{
				{1,2},
				{1,2,3,4},
				{1,3,2},
				{100,1,2,3},
				{1,100,2,3},
				{1,2,100,3},
				{1,2,3,100},
				{1,200,300,2},
				{100,200,300,4},
				{1,200,3,400},
				{100,200,300,400},
				{1,2,4,100,4},
				{1,2,100,3,4,5,6,200},
				{1,1,20,30},
				{1,2,2,3},
				{1,2,3,3}
			};
		
		int[][] testFalse =
			{
				{},
				{1},
				{2,1},
				{1,1},
				{1,3,2,1},
				{1,5,2,7,4,5},
				{1,5,2,3,4,9,5,6,7},
				{100,1,2,3,4,200,5,6},
				{1,100,2,3,4,5,200,6},
				{1,100,2,3,4,5,200,2},
				{10,20,30,5,6},
				{1,1,1,10,20},
				{1,2,3,3,3,4,5},
				{1,2,3,4,5,5,5},
				{10,20,30,1,30},
				{4,3,2,1}
			};

The results for the OP's algorithm:

 PASS   true   sec: 0.000  [1, 2]
 PASS   true   sec: 0.000  [1, 2, 3, 4]
 PASS   true   sec: 0.000  [1, 3, 2]
*FAIL*  false  sec: 0.000  [100, 1, 2, 3]
*FAIL*  false  sec: 0.000  [1, 100, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 100, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 100]
 PASS   true   sec: 0.000  [1, 200, 300, 2]
 PASS   true   sec: 0.000  [100, 200, 300, 4]
 PASS   true   sec: 0.000  [1, 200, 3, 400]
 PASS   true   sec: 0.000  [100, 200, 300, 400]
 PASS   true   sec: 0.000  [1, 2, 4, 100, 4]
*FAIL*  false  sec: 0.000  [1, 2, 100, 3, 4, 5, 6, 200]
 PASS   true   sec: 0.000  [1, 1, 20, 30]
 PASS   true   sec: 0.000  [1, 2, 2, 3]
 PASS   true   sec: 0.000  [1, 2, 3, 3]
*FAIL*  true   sec: 0.000  []
*FAIL*  true   sec: 0.000  [1]
*FAIL*  true   sec: 0.000  [2, 1]
*FAIL*  true   sec: 0.000  [1, 1]
 PASS   false  sec: 0.000  [1, 3, 2, 1]
 PASS   false  sec: 0.000  [1, 5, 2, 7, 4, 5]
 PASS   false  sec: 0.000  [1, 5, 2, 3, 4, 9, 5, 6, 7]
 PASS   false  sec: 0.000  [100, 1, 2, 3, 4, 200, 5, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 6]
 PASS   false  sec: 0.000  [1, 100, 2, 3, 4, 5, 200, 2]
 PASS   false  sec: 0.000  [10, 20, 30, 5, 6]
 PASS   false  sec: 0.000  [1, 1, 1, 10, 20]
 PASS   false  sec: 0.000  [1, 2, 3, 3, 3, 4, 5]
 PASS   false  sec: 0.000  [1, 2, 3, 4, 5, 5, 5]
 PASS   false  sec: 0.000  [10, 20, 30, 1, 30]
 PASS   false  sec: 0.000  [4, 3, 2, 1]

[Liutauras Vilda]

Junilu, thanks for great tests. Carey, thanks for reporting your progress - it made me look further to this. Have both cows. Cow for OP too for giving us chance to have fun.

I've fixed my algorithm as per failing cases. Since the beginning problem looked very simple, to come up with a starting algorithm took me around 10 minutes, oh well, I guess simple problem is simple as long as you have all possible different scenarios covered within tests.
On friday I wrote for myself around 15 test cases, but haven't covered failing ones - that gave me a lesson, how poor test cases can ruin the algorithm correctness and make you believe algorithm is free of bugs.

Now, that algorithm became a bit more complicated, I'm no longer happy how it reads. So next step of mine going to be a refactoring.

Would be interesting to know OP's progress if he finished and got all tests passing version, so we could share our algorithms and then might continue discussion on how to make them more elegant.

Running LiutaurasAlgorithm

Smallest one that will pass: [1, 2]
Passed (0 secs 144 millis)

Drop high number, first element: [30, 1, 2]
Passed (0 secs 0 millis)

Drop high number, middle element: [1, 30, 2]
Passed (0 secs 0 millis)

Drop low number, middle element: [10, 20, 30, 2, 40, 50]
Passed (0 secs 0 millis)

Drop low number, last element: [10, 20, 30, 2]
Passed (0 secs 0 millis)

Drop repeated number, first element: [1, 1, 20, 30]
Passed (0 secs 0 millis)

Drop repeated number, middle element: [1, 2, 2, 3]
Passed (0 secs 0 millis)

Drop repeated number, last element: [1, 2, 30, 30]
Passed (0 secs 0 millis)

Drop high number in middle but repeated number at start: [1, 100, 1, 2, 3]
Passed (0 secs 0 millis)

Drop high number in middle but repeated number in middle: [1, 2, 100, 2, 3]
Passed (0 secs 0 millis)

Drop high number in middle but still not increasing sequence: [2, 4, 6, 3, 5, 7]
Passed (0 secs 0 millis)

Drop low number in middle but repeated number in middle: [10, 20, 30, 1, 30, 40, 50]
Passed (0 secs 0 millis)

Drop low number in middle but repeated number at end: [10, 20, 30, 1, 30]
Passed (0 secs 0 millis)

Not enough elements: [1]
Passed (0 secs 0 millis)

Smallest one that will fail: [2, 1]
Passed (0 secs 0 millis)

Longer one that will fail: [4, 3, 2, 1]
Passed (0 secs 0 millis)

Too many elements out of sequence from start: [10, 2, 10, 3, 4, 5, 6]
Passed (0 secs 0 millis)

Too many elements out of sequence in middle: [10, 20, 1, 30, 1, 40, 50, 60]
Passed (0 secs 0 millis)

Too many elements out of sequence at end: [10, 20, 30, 40, 50, 1, 60, 1]
Passed (0 secs 0 millis)

Too many repeats at start: [1, 1, 1, 10, 20]
Passed (0 secs 0 millis)

Too many repeats in middle: [1, 2, 3, 3, 3, 4, 5]
Passed (0 secs 0 millis)

Too many repeats at end: [1, 2, 3, 4, 5, 5, 5]
Passed (0 secs 0 millis)

Fail fast with two drops at front of long (1,000,000 elements) array: [0, 1, 2, 1, 4, 5, 4, 7, 8, 9, 10, 11]
Passed (0 secs 0 millis)

Second drop at end of long sequence: [0, 1, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11]
Passed (0 secs 1 millis)

Time to traverse a long (268,435,455 elements) sorted array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Passed (0 secs 154 millis)

25 of 25 tests passed