# Validate Subsequence

Learn to efficiently determine whether a sequence is a subsequence of another through a step-by-step approach.

array
easy

Published At

6/4/2021

Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.

A subsequence of an array 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 array. For instance, the numbers `[1, 3, 4]` form a subsequence of the array `[1, 2, 3, 4]`, and so do the numbers `[2, 4]`. Note that a single number in an array and the array itself are both valid subsequences of the array.

### Sample Input

js
``````array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]``````
js
``````array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]``````

### Sample Output

js
``true``
js
``true``

### Hints

Hint 1

You can solve this question by iterating through the main input array once.

Hint 2

Iterate through the main array, and look for the first integer in the potential subsequence. If you find that integer, keep on iterating through the main array, but now look for the second integer in the potential subsequence. Continue this process until you either find every integer in the potential subsequence or you reach the end of the main array.

Hint 3

To actually implement what Hint #2 describes, you'll have to declare a variable holding your position in the potential subsequence. At first, this position will be the 0th index in the sequence; as you find the sequence's integers in the main array, you'll increment the position variable until you reach the end of the sequence.

Optimal Space & Time Complexity

`O(n) time` | `O(1) space` - where `n` is the length of the array

Solution-1
js
``````function isValidSubsequence(array, sequence) {
let count = 0
for (let num of array) {
if (num === sequence[count]) {
count++
continue
}
}
if (count == sequence.length) {
return true
}
return false
}``````
Solution-1
js
``````function isValidSubsequence(array, sequence) {
let count = 0
for (let num of array) {
if (num === sequence[count]) {
count++
continue
}
}
if (count == sequence.length) {
return true
}
return false
}``````
Solution-2
js
``````function isValidSubsequence(array, sequence) {
let arrayIndex = 0,
seqIndex = 0
while (arrayIndex < array.length && seqIndex < sequence.length) {
if (array[arrayIndex] === sequence[seqIndex]) seqIndex++
arrayIndex++
}
return seqIndex === sequence.length
}``````
Solution-2
js
``````function isValidSubsequence(array, sequence) {
let arrayIndex = 0,
seqIndex = 0
while (arrayIndex < array.length && seqIndex < sequence.length) {
if (array[arrayIndex] === sequence[seqIndex]) seqIndex++
arrayIndex++
}
return seqIndex === sequence.length
}``````

🌊

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.