Given two non-empty arrays of integers, write an algorithm that determines whether the second array is a subsequence of the first one.

Overview

As long, we keep finding the elements of the arbitrary array in the input array and in order, we are good.

Flow Diagram

Time Complexity

Worst case scenario. we will need to go through the main array once, that would be O(n) time complexity.

Space Complexity

Space complexity is O(1). That is because we are just using a couple of variables, however the amount of the variables will be the same, for any size of input array. You got to love O(1).

Java Source Code

Solution 1 - With While loop

 public boolean isValidWithWhile(final int[] array,final int[] sequence) {
        var arrayIndex = 0;
        var seqIndex = 0;

        while(arrayIndex < array.length && seqIndex < sequence.length) {
            final var hasFoundMatch = array[arrayIndex] == sequence[seqIndex];

            if(hasFoundMatch) {
                seqIndex++;
            }

            arrayIndex++;
        }

        return seqIndex == sequence.length;
    }

Solution 2 - With For loop

 public boolean isValidWithFor(final int[] array, final int[] sequence) {
        var seqIndex = 0;

        for(int value : array) {
            if(seqIndex == sequence.length) {
                break;
            }

            final var hasFoundMatch = sequence[seqIndex] == value;

            if(hasFoundMatch) {
                seqIndex++;
            }
        }

        return seqIndex == sequence.length;
    }

Conclusion

A sequence works in a way a collection never can.

George Murray