Validate Subsequence

A corgi smiling happily

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

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

Sample Output

1true

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
1function isValidSubsequence(array, sequence) {
2 let count = 0
3 for (let num of array) {
4 if (num === sequence[count]) {
5 count++
6 continue
7 }
8 }
9 if (count == sequence.length) {
10 return true
11 }
12 return false
13}
Solution-2
1function isValidSubsequence(array, sequence) {
2 let arrayIndex = 0,
3 seqIndex = 0
4 while (arrayIndex < array.length && seqIndex < sequence.length) {
5 if (array[arrayIndex] === sequence[seqIndex]) seqIndex++
6 arrayIndex++
7 }
8 return seqIndex === sequence.length
9}

🌊

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 🙏

Subscribe to my newsletter

Get email from me about my ideas, full-stack development resources, tricks and tips as well as exclusive previews of upcoming articles.

No spam. Just the highest quality ideas you’ll find on the web.