compare order of two arrays

Question

Say I have this default array in JavaScript:

const default = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']

I have this array provided by the user:

const user_arr = ['red', 'green', 'violet']

I need to compare these two arrays and validate that the user array is in the correct order (i.e. I am allowed to skip levels, but reverse order is not allowed).

So the following arrays would be valid:

['red', 'orange', 'violet']
['yellow', 'blue']
['green', 'indigo', 'violet']

There arrays would be invalid:

['red', 'violet', 'orange']
['green', 'violet', 'yellow]

Is this possible without using complex tree data structures?

Answer 1

Here I map each element in the user array to its index in the proper array.

The array of indexes is checked to make sure it's in ascending order.

note that "default" is a javascript keyword and isn't a valid variable name

const proper = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']

const isValid = (arr) => {
  
  const isAscending = (arr) => arr.every((el, i, a) => 
    i === a.length - 1
    ? true
    : el < a[i + 1]
  );

  return isAscending(arr.map(el => proper.indexOf(el)));
}

const user_arr = ['red', 'green', 'blue']

console.log(isValid(user_arr));
console.log(isValid(['red', 'indigo', 'orange']));

Answer 2

I don't know if it is the most efficient way, but this should work:

/**
 *  
 * @param {string[]} ref
 * @param {string[]} array
 * @return {boolean}
 */
function checkValidity(ref, array) {
  let prev = 0;
  for (let i = 0; i < array.length; i++) {
    const current = ref.findIndex((elt) => elt === array[i]);
    if (current >= prev) prev = current;
    else return false;
  }
  return true;
}

Answer 3

This approach uses a Map which maps the value of an item to its index within the array.

Using that map we then we check for every element in a user supplied array whether we have that item in our original array. If we have not, the user array is invalid. If it is a known item we need to get its position in the original array and check if it greater than the previous position we have checked. If it is, everything is fine, if it is not, the user array is invalid.

Remarks on solution

This solution does not allow for duplicate values as it checks for <, not <=. If you have duplicate values in your original array the latest of all occurrences of that duplicate value will determine its position in the array. Currently this implementation does not accept empty arrays but one could easily change that so an empty array would be accepted.

Complexity

The advantage of using a Map is the speedup for the lookup of the index which can be done in O(1). Therefore, one needs O(n) time with n being the number of items in the original array once to initialize the Map. Then one can use that Map to check whether a user array is valid in worst case O(m) time (e.g. for a valid array) where m is the number of items in a user supplied array. Using just arrays and methods like indexOf() or find() will have a worst case time complexity of O(m * n). For small arrays such as yours those things won't really matter though.

const order = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
const indexToValue = new Map();
order.forEach((item, idx) => indexToValue.set(item, idx));

const validArrays = [
  ["red"],
  ["red", "orange", "violet"],
  ["yellow", "blue"],
  ["green", "indigo", "violet"],
];

const invalidArrays = [
  ["red", "violet", "orange"],
  ["green", "violet", "yellow"],
];

/**
 *
 * @param {Array<string>} userArray
 * @param {Map<string, number>} indexToValue
 * @returns
 */
function checkCorrectness(userArray, indexToValue) {
  if (!Array.isArray(userArray) || userArray.length === 0) return false;
  let prev = -1;
  return userArray.every((item) => {
    // an unknown item is in the user array so it is invalid 
    if (!indexToValue.has(item)) return false;
    // get index of the element in the original array
    const idxInOrig = indexToValue.get(item);
    // if the current index is smaller than the previous index -> invalid! stop immediately 
    if (idxInOrig < prev) return false;
    // everything is fine current index is bigger than previous -> continue with next one
    prev = idxInOrig;
    return true;
  });
}

console.log("Invalid arrays")
invalidArrays.forEach(invalid => console.log(checkCorrectness(invalid, indexToValue)));
console.log("Valid arrays")
validArrays.forEach(valid => console.log(checkCorrectness(valid, indexToValue)));