# Leetcode: Problem #2 — Validate Subsequence

Given two non-empty arrays of integers, our goal is to write a function that establishes whether the second array is a valid subsequence of the first array. A valid subsequence of an array is classified as a set of numbers that aren’t necessarily adjacent in the array but are in the same order as they appear in the array. For example, [2, 5, 6] and [2, 6] are both considered as valid subsequences of the array [2, 3, 4, 5, 6]. It is also important to note that [2] and [2, 3, 4, 5, 6] are both valid subsequences of the array.

Sample:

Input array → [3, 6, 23, 7, 2, 4]

Sequence → [3, 7, 4]

Output → True

There are 2 ways to solve this problem, one approach utilizing a while loop and the other approach implementing a for-loop. Furthermore, each of these approaches has a space-time complexity of O(n) time and O(1) space. We’ll explore each approach one by one below.

# While Loop Approach

arrayIndex = 0

sequenceIndex = 0

Here we are creating 2 *pointers*, one to keep track of our current position or iteration in the array and the other with the potential valid subsequence.

By using a while loop, we will be conducting a linear search as we traverse or go through each element in the given input array. The time complexity is O(n) where n is the length of the main input array due to utilizing a single while loop.

while arrayIndex < len(array) and sequenceIndex < len(sequence):

We create our while loop and each loop requires a condition to check for, and in this case, we are checking if the 2 pointers that we defined earlier are both less than the total length or size of the given input array and subsequence.

Essentially, our 2 pointers serve as a way for us to track where we are iterating at a given point in time, or in other words, the index. Therefore, we want to make sure that our pointers or indices are less than the length of the given input array and subsequence because no such values exist at the indices specified.

It’s also important to note that we are using the boolean keyword **and*** *not* ***or** because we are making sure that both conditions specified are being satisfied, not just one. If the arrayIndex is not less than the total length of the given input array (if it is equal to or greater than the total length of the given input array), then we must have traversed through all of the given input array and if the sequenceIndex is not less than the total length of the sequence array (if it is equal to or greater than the total length of the sequence array), then we must have found a valid subsequence from the given input array.

if array[arrayIndex] == sequence [sequenceIndex]:

[ → ]¹ sequenceIndex += 1¹[ → ] indicates an indentation.

Here we have an if statement that checks if the value in the given input array located in the arrayIndex is equivalent to the value in the sequence array located in the sequenceIndex. In other words, if we find a match between the values in the sequence array and given input array, then we want to add 1 to our sequenceIndex. The reason why we want to increment 1 to our sequenceIndex is that it makes our sequenceIndex not only serve as a pointer or an index but also as a count so we can also keep a tally of how many matches there were between the sequence array and the given input array.

arrayIndex += 1

Similarly, we increment 1 to our arrayIndex at each iteration in our while loop because the given input array serves as the main array that we are traversing. On the other hand, we only increment the sequenceIndex by 1 if the if condition above is satisfied.

return sequenceIndex == len(sequence)

After we exit from our while loop, we are returning a boolean value whether if the sequenceIndex is equal to the total length of the sequence array. Earlier, I mentioned that sequenceIndex serves as a count, and this is where you can see that more clearly because if the sequenceIndex is equal to the total length of the sequence array, this means that we found each value or element within the sequence array in the given input array, which forms a valid subsequence.

# For-Loop Approach

sequenceIndex = 0

Similarly with the while loop solution, the for-loop approach also implements a pointer called sequenceIndex, which is set to an index of 0. This is usually a good indicator that we will be utilizing this pointer to perform some sort of linear search with a for or while loop.

for value in array:

[ → ] if sequenceIndex == len(sequence):

[ → ][ → ] break

[ → ] if sequence[sequenceIndex] == value:

[ → ][ → ] sequenceIndex += 1

Here we create our for loop iterating through each element in the given input array, and at each iteration, we are checking for 2 separate conditions:

- If the sequenceIndex is equal to the length of the sequence array, we know that have found a valid subsequence and therefore want to
*break*or - If the value in the sequence array at the sequenceIndex is equal to the current value we are iterating in our given input array, then we want to increment the sequenceIndex by 1, which goes back to what we discussed earlier about the sequenceIndex serving as a count.

return sequenceIndex == len(sequence)

Likewise with the while loop solution above, after we exit from our for-loop, we are returning a boolean value whether the sequenceIndex is equal to the total length of the sequence array. Earlier, I mentioned that sequenceIndex serves as a count, and this is where you can see that more clearly because if the sequenceIndex is equal to the total length of the sequence array, this means that we found each value or element within the sequence array in the given input array, which forms a valid subsequence.

**If you made it here, I hope you found this insightful and definitely be proud of what you were able to learn and achieve. If you have any lingering questions or comments, please don’t feel afraid to ask or connect with me on social media!**