Given this arrays I want to check if "sequence" is a subsequence of "array", meaning all the numbers exist in the original array and in the same order:
array = [5, 1, 22, 25, 6, -1, 8, 10];
sequence = [1, 6, -1, 10];
Not sure why my code doesn't work.
function isValidSubsequence(array, sequence) {
let seqIdx = 0;
let arrId = 0;
for (const value of sequence ){
if (seqIdx === sequence.length) break;
if (array[arrId] === value) {
seqIdx++;
arrId++;
}
}
return seqIdx === sequence.length
}
Your solution doesn't work because it never moves past the first entry in array. You never increment any of your indexes unless the sequence value matches array[arrId].
I'd use a combination of Array.prototype.indexOf() and Array.prototype.slice() to create a shrinking window of array as you search. If you ever reach an iteration of sequence that cannot be found, you know it fails the test
function isValidSubsequence(array, sequence) {
let slice = array.slice(); // start with a shallow copy
for (const value of sequence) {
let index = slice.indexOf(value); // find the next sequence value
if (index === -1) {
return false; // not found, return false immediately
}
slice = slice.slice(index); // shrink the window
}
return true;
}
const array = [5, 1, 22, 25, 6, -1, 8, 10];
const sequence = [1, 6, -1, 10];
console.log("valid sub-sequence:", isValidSubsequence(array, sequence))
console.log("out of order:", isValidSubsequence(array, [25, 22]))
console.log("unknown elements:", isValidSubsequence(array, [5, 11]))Remove arrIdx.
In a for...of loop the index of array isn't needed in this case since value progresses on each iteration.
Remove the first flow control statement.
if (seqIdx === sequence.length) break;
There's no need to interupt the loop. The Boolean returned outside of the loop is sufficient.
Change the second flow control statement to monitor sequence[seqIdx] not array
if (sequence[seqIdx] === value) {
seqIdx++;
}
The key to this algorithm is to progress through array one number at a time (as is the norm), but not the sequence. The counter, seqIdx, only progresses on a match so basically if sequence ends before or at the end of the loop it is a valid subsequence.
const arr = [5, 1, 22, 25, 6, -1, 8, 10];
const seq = [1, 6, -1, 10];
function isValidSubsequence(array, sequence) {
let seqIdx = 0;
for (const value of array) {
if (sequence[seqIdx] === value) {
seqIdx++;
}
}
return seqIdx === sequence.length;
};
console.log(isValidSubsequence(arr, seq));You can achieve it in a simple way by finding the index of sequence array elements from the original array and then check if the indexed array is sorted or not.
Demo :
const array = [5, 1, 22, 25, 6, -1, 8, 10];
const sequence = [1, 6, -1, 10];
// Find index of the elements from the original array.
const indexArr = sequence.map((item) => array.indexOf(item));
// Now test if this indexed array is sorted or not to check if sequence array having same order as per the original array.
function isSorted(arr) {
var i = 0;
var last = arr.length - 1;
return (function check() {
return (i >= last) || (arr[i] <= arr[++i] && check());
})();
}
console.log(isSorted(indexArr))