In this problem, we're given an array and a sequence (also an array), and we are checking if the sequence is a subsequence of the array. An array is a subsequence of the original array if it is made up entirely of elements from the original array and if the elements are still in the same order. An array is still a subsequence if it contains all of the element of the original array, without any deletions or changes in the order of the elements.
Problem
Given an array and a sequence (which is another array), check if the sequence is in fact a subsequence of the array. Return true if it's a subsequence, and false if not.
A subsequence of an array is a new array which is formed from the original array by deleting some (or none) of the characters without changing the order of the elements in the array.
Ex. [3, 7, 4, 9] is a subsequence of [1, 3, 2, 7, 8, 4, 5, 9]
Notice how integers in the larger array are in the same order as in the subsequence, even though they are not necessarily right next to each other in the larger array.
Ex. [6, 8, 9] is not a subsequence of [1, 3, 2, 7, 8, 4, 5, 9] because the larger array does not contain 6.
Approach
We will use a while loop to iterate through the entirety of the original array, checking for the integers in the given sequence. We initialize pointers for both the array and sequence, increasing each pointer by 1 as we loop. The while loop will continue executing as long as the pointer for the array is less than the length of the array, AND as long as the pointer for the sequence is less than the length of the sequence. These pointers will keep track of our positions in the array and sequence. The pointer for the sequence will increase only if there is a match, that is the current element we are looking at in the sequence is the same as the element we are looking at in the array. The pointer for the array will increase with each iteration because we have to look through the entire array to find the elements in the sequence in order, since order matters. Our problem asks for a boolean as the answer, so we return true if the sequence pointer value is the same as the length of the sequence itself, meaning it is a true subsequence, and false otherwise.
Solution
Initialize our pointers to keep track of our positions in the array and sequence.
function checkValidSubsequence(array, sequence) {
let arrayIndex = 0;
let sequenceIndex = 0;
}
Create a while loop using the conditions mentioned in the approach.
function checkValidSubsequence(array, sequence) {
let arrayIndex = 0;
let sequenceIndex = 0;
while (arrayIndex < array.length && sequenceIndex < sequence.length) {
}
}
If the element we are currently on in the sequence matches the element in the array, then we increment sequenceIndex by 1.
function checkValidSubsequence(array, sequence) {
let arrayIndex = 0;
let sequenceIndex = 0;
while (arrayIndex < array.length && sequenceIndex < sequence.length) {
if (sequence[sequenceIndex] === array[arrayIndex]) {
sequenceIndex++;
}
}
}
Inside of the while loop, but outside of the if statement, increase the arrayIndex by 1 so we continue searching through the array.
function checkValidSubsequence(array, sequence) {
let arrayIndex = 0;
let sequenceIndex = 0;
while (arrayIndex < array.length && sequenceIndex < sequence.length) {
if (sequence[sequenceIndex] === array[arrayIndex]) {
sequenceIndex++;
}
arrayIndex++;
}
}
Lastly, we set up a boolean expression to return true or false dependent on if we have a subsequence of the given array. If the sequenceIndex is equal to the length of the sequence, we return true, and false otherwise. This is outside of the while loop.
function checkValidSubsequence(array, sequence) {
let arrayIndex = 0;
let sequenceIndex = 0;
while (arrayIndex < array.length && sequenceIndex < sequence.length) {
if (sequence[sequenceIndex] === array[arrayIndex]) {
sequenceIndex++;
}
arrayIndex++;
}
return sequenceIndex === sequence.length;
}
Resources
Top comments (0)