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

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
const array = [1, 2, 3, 4, 5, 6]
let pointer = 0 #set position of pointer
#return 5while (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
}

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

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.

I do software engineering