How to Validate a Subsequence in an Array? by Danny Reina

Optimized Solution

Intent

I am on the path of sharpening my algorithm problem solving skillset. Along the way I want to share with you how one starts from zero and progressively gets better. This article will show you how I learned to solve this common algo problem typically called validate subsequence in an array.

Problem

Difficulty: Easy

Given two inputs, the first an array of integers the second a smaller array of integers, write a function that determines if the second array is a subsequence of the first array. For example.

const arrOfNums = [1, 3, 5, 9, 12, 18]
const validSequence = [3, 12, 18]
const notValidSequence = [3, 12, 15, 18]
function isValidSubSequence(array, sequence){                                           
   //write algo here
   //output should be either true or false
}
isValidSubSequence(arrOfNums, validSequence) => true
isValidSubSequence(arrOfNums, notValidSequence) => false

What is a valid subsequence?

A subsequence is a set of intergars that appear in the original array and in the same order. Keep in mind, that single integers are valid subsequences and the integers in the sequence array do not have to appear adjacent. Additionally, for this problem, the sequence array is typically smaller than the original array, since traversing on a sequence array that is larger than the original array will create problematic edge cases that is discussed in the solution section of this article. A subsequence example is provided below.

[2, 4, 0, 5, -1, 10] => original array
[2, 4, 0, 5, -1, 10] => is a subsequence
[2, -1, 10] => is a subsequence
[4, 5, 10] => is a subsequence => numbers do not have to be adjacent [2] => is a subsequence
[-1] => is a subsequence
[2, 4, 0, 5, -1, 10, 11] => is not a subsequence
[2, 4, 0, 100000, -1, 10] => is not a subsequence
[0, 2, 4, 0, 5, -1, 10] => is not a subsequence

Approach

My initial thought was to traverse both arrays and compare the element from the sequence array to each element of the original array. If there is a match then I would continue traversing until the entire sequence array is traversed. If the entire sequence is traversed then I know I have a subsequence. However, I quickly discovered an issue, what if the second element in the sequence array is in the original array but appears before the first number in the sequence array.

const array = [1, 3, 5, 6]
const sequence = [3, 1, 5, 6]
// All numbers are present but do not match the order therefore 
// sequence is not a subsequence of array

To solve this, I used a method called pointers which is commonly used in algo problem solving. The idea is initialize a pointer that represents the position on an array, and, if you want to change the position of that pointer to point at a different element on the array then you increment the value of the pointer while you are traversing a different array. For example.

const array = [1, 2, 3, 4, 5, 6]
let pointer = 0 #set position of pointer 
#return 5
while (pointer < array.length) {
   if (array[pointer] === 5) {
       return array[pointer]
   }
   pointer ++ 
//increase pointer value to move pointer position to the next //element while traversing the array
}

Therefore, my next approach is to utilize a pointer to compare elements between the original array and potential sequence array. If the the elements between the sequence and original array match then I would move the position on the sequence array to compare the next element in the sequence array to the next element in the original array and continue until the entire sequence array is compared to the original array. If the entire sequence array is traversed then I know that it is a true subsequence of the original array if it does not then it is not.

Solution

Since we have array inputs and would have to traverse an array, we can imploy a for or while loop for traversing. Additionally, we will use a pointer to keep track of our position on the sequence array.

const arrOfNums = [1, 3, 5, 9, 12, 18]
const validSequence = [3, 12, 18]
const notValidSequence = [3, 12, 15, 18]
function isValidSubSequence(array, sequence) { 
                                
  let sequenceIdx = 0 // initialize pointer/position
  for (let i = 0; i < array.length; i++) {
       if (sequenceIdx === sequence.length) {
           return true
       }
       
       if (sequence[sequenceIdx] === array[i]) {
           sequenceIdx++ // if elements match move position
       }
   }
   
   // returns true if entire sequence array is traversed
   return sequenceIdx === sequence.length 
}
isValidSubSequence(arrOfNums, validSequence) => true
isValidSubSequence(arrOfNums, notValidSequence) => false

Why use a pointer on the sequence array and not the original array?

What if we decide to traverse the sequence array instead of the original array? We could but we wouldn’t be able to access all the elements of the original array except for one specific case. Going back to our definition of a subsequence, in general a subsequence has to be either the exact same length or smaller than the original array. Therefore, if we traverse the sequence and if it matches the original array in size then only in that case can the function return true if a subsequence is present. However, usually, the original array is larger than the sequence array. So, in order to satisfy the subsequence requirements, we have to traverse the original array, not the sequence array.

Time Space Complexity

Since the length of the traversing operation depends on the length of the array then our time complexity is linear time or in big O notation O(n). Our space complexity relies on the size of our initialized data structures. Since we are only initializing a pointer and never increasing its size, or in other words increasing its size in memory allocation, then we can say space complexity is constant or O(1). Keep in mind, that when we are increasing the value of our pointer its not using more memory to store that new number, rather its accessing the already initialized pointer variable and assigning it a new value thus preserving constant space.

Conclusion

It is important to create a solid foundation on what a subsequence is since subsequences are a common topic in move advanced algorithms that are presented in technical interviews. I will cover these more advanced algorithms in the future.

Finally, I want to stress that problem solving these algorithms can be difficult and is totally natural to feel as if you hit a wall. If you found this article helpful or informative please share your thoughts below.