Can You Form This Array? Check Using Concatenation

Leetcode January Challenge #1: Check Array Formation Through Concatenation (Javascript)

Photo by Charles Deluvio on Unsplash

Prompt:

• arr is a distinct array
• you are not allowed to reorder the integers in each array pieces[i]
• form arr by concatenating the arrays in pieces in any order

Examples:

ex 1)

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

ex 2)

Input: arr = [2, 82, 79, 95, 28], pieces = [[2], [82], [28], [79, 95]]
Output: true

My Solution:

• Check if each element of pieces exists in arr . Let’s call the element piece (in other words, let piece = pieces[i]).
• Notice thatpiece is an array of at least one number.
• If piece has only one number, simply check if the number exists in arr.
• Else (to be specific, piece has more than one number), find the index of the first element. Then, cut arr by the length of piece from the index you found. Compare if the cut array and piece are the same using helper function.

// helper function to check if two arrays are the same
function sameArray(arr1, arr2) {
  // no need to iterate through array if lengths are different
  if (arr1.length !== arr2.length) {
    return false;
  }
for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] !== arr2[i]) {
      return false;
    }
  }
return true;
}

function canFormArray(arr, pieces) {
  for (let p of pieces) {
    if (p.length === 1) {
      if (!arr.includes(p[0])) return false;
    } else {
      let i = arr.indexOf(p[0]);
      if (!sameArray(arr.splice(i, p.length), p)) return false;
    }
  }
  return true;
};

Reflection:

Difficulty : ★☆☆☆☆

Runtime : (my runtime beats 94.72% of javascript submissions)

Note : We are iterating through the loop twice. Once through pieces and once through arr. Everything else takes constant time. So it takes O(n + m).