May 10, 2021
Validate Subsequence
Algo Expert — Easy
Today we are going to go over a simple coding question.
Problem:
Given two arrays, we need to determine if the second array is a subsequence of the first array.
Subsequence: is a set of numbers that aren't necessarily adjacent in the array but that are in the same order as they appear in the first array.
Example:
first array = [5, 1, 22, 25, 6, -1, 8, 10]
second array= [1, 6, -1, 10]
Output = true
All the numbers in the second array appear in the first in the same order.
Solution:
Based on the question we can notice that order is very important for this problem. Therefore we will no be sorting anything here.
function isValidSubsequence(array, sequence) {
let fIdx = 0
let sIdx = 0while (fIdx < array.length && sIdx < sequence.length) {
if (array[fIdx] === sequence[sIdx]) sIdx++
fIdx++
}
return sIdx === sequence.length
}
As you can see on the solution above we are declaring two variables that hold the index. We will start both at 0. After we will go in a while loop that will be based on the length of both arrays to make sure we don't go outside of them. In the loop, we are going to check the value in the first array at index [0] and the value of the second array at index [0] if they are the same then we will increment the index. If they are not the same then we will increment the index of the first array. After we will return a true or false value depending on if everything in the second array was found in the first array. I hope this small walk-through was helpful to see how to solve this question and give you a little insight into using a different way of looping through an array that saves time. This solution is O(n) time and O(1) space.
