I Need Some Validation: Validating Sub-sequences

What is a sub-sequence? It is a set of numbers in an array that aren’t necessarily adjacent to each other, but are in the same order they appear in the “main” array. So in order to figure out if an array is the sub-sequence of a larger or main array we need to compare the two to each other.

In the example below we can see 32 in the sub-sequence is included in the array. Seven and -4 are also included in the sub-sequence and the array. All of which are in the correct order as well. Despite 32 not being adjacent to 7 the sub-sequence is still a sub-sequence. But how do we make a function that can validate this?

Creating the Function

To make a function to validate the sub-sequence, the function is going to need to take in two inputs. These inputs would be the sub-sequence array and the array we are comparing the sub-sequence to. We are going to have to traverse through each array to compare numbers. Keeping time complexity in mind, we know we don’t want to do something as inefficient as a nested loop of some kind. We can, however, create a variable that will track the index of one of the arrays and then create a loop that iterates over the other array, incrementing the variable each time we complete one instance of the loop. The set up would look something like this in JavaScript:

SeqI is our variable to keep track of the index for the sub-sequence. It is set to 0 because we want to start at the beginning of the sub-sequence array and then increment by one every time we find a number in the main array that matches that specific number in the sub-sequence array. In the for loop we are looking at one number at a time in the main array. If the number (num) doesn’t match the value we are looking for in the sub-sequence array, then we want the loop to advance to the next number in the main array, but keep looking for the same number form the sub-sequence. We can write this by using an if-statement that advances the index we are tracking with our seqI variable.

There’s still some code missing inside the for loop. We also want to stop looking through the main array if we have already gone through our entire sub-sequence array. To account for that we can add another if-statement before the one that advances the seqI variable. It would cause the loop to break if the index we are tracking is the same length as the sub-sequence array. If the index and sub-sequence array length match each other that means we have found every sub-sequence value in order in the main array.

How do we validate?

Now that we know how to run through the loop, how are we going to validate the sub-sequence? Well, if we get through the for-loop and the seqI variable isn’t the same as the sub-sequence array length, then that means we went through the entire main array and didn’t finish finding all the sub-sequence values. This would cause the function to return false. If the seqI variable is equal to the sub-sequence array length, then we did find all the sub-sequence values and the function will return true.

I learned how to do this solution on algoexpert.io. If you haven’t taken a look at their data structures course I highly recommend it.