Check if an array is a subsequence of another array-CodePudding

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
}

CodePudding user response：

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]))

CodePudding user response：

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));

CodePudding user response：

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))