Validating a Subsequence

Today we will be going over how to see if an array is a subsequence of another array. A subsequence of an array is a set of numbers that aren’t necessarily adjacent in the array but appear in the same order as they are in the array.

So the following would be return true as being a subsequence.

[1, 2, 3, 4, 5] / [1, 3 ,5]

While the following would not.

[1, 2, 3, 4, 5] / [6, 7]

This problem may seem confusing at first but it’s actually quite simple. The approach we can take to solve this is to loop through both arrays at once. Keeping track of their length and ending once we reach the end of both arrays but the sequences index will only increment once we see a number from it in the input array. It sounds more complex than it is so lets start some code to show how this would look.

This is a great start for our problem and it should give a nice view of what we’re going to do in the rest of this problem to solve it. There are only a few more lines of code we need to add to finish up this problem. While we are in our ‘while’ loop we need to increment the arrayIndex value for each number we loop over. We also need to check to see if the number we are currently at in our loop in the array input is the same number we are at in our sequence input, if it is we increment the sequenceIndex variable by 1. That would look like this in code..

Here we have an almost finished solution, we just need to add one more line of code. Basically the only thing we have left to do is to check and see if the sequenceIndex variable is equal to the sequences length and this will either return true or false, remember we only incremented the sequenceIndex when we saw the variable in both the array and the sequence. The final code would look like this..

And thats our problem, another week, another one solved! Lets meet back here next week to solve another classic problem. Until then, take care!