JavaScriptでソース配列の連結によりターゲット配列を形成できるか判定する方法

問題の概要

相異なる整数で構成される配列 arr(ターゲット配列)と、整数配列を要素として持つ配列 sourceArr(ソース配列)が与えられます。sourceArr 内の各サブ配列に含まれる整数も、全体として重複がありません。

目的は、sourceArr に含まれるサブ配列を任意の順序で連結することで、ターゲット配列 arr を完全に再現できるかどうかを判定する関数を実装することです。

重要な制約として、各サブ配列内部の要素を並べ替えることはできません。自由に決められるのは、サブ配列を連結する順序だけです。形成が可能であれば true、不可能であれば false を返します。

具体例

const arr = [23, 67, 789];
const sourceArr = [[23], [789, 67]];

この場合、結果は false になります。サブ配列 [789, 67] 内の要素は並べ替えられないため、789 より先に 67 を配置することができず、ターゲット配列 [23, 67, 789] を作れないからです。

アルゴリズムの考え方

この問題は、次の手順で効率よく解くことができます。

• 先頭要素のマップ作成: 各サブ配列の最初の要素をキーとして、そのサブ配列が sourceArr のどこにあるかを記録したマップ(Map)を作成します。整数が全体で一意であるため、先頭要素も必ず一意になります。
• ターゲット配列の走査: arr を先頭から順に見ていき、現在位置の値で始まるサブ配列をマップから探します。存在しなければ即座に false を返します。
• 逐次照合: 見つかったサブ配列の要素を先頭から順に、arr の対応する位置と比較します。1つでも不一致があれば false を返します。
• 完了判定: 照合がすべて成功し、arr の末尾まで到達できれば true を返します。

計算量は、ターゲット配列の長さを n とすると O(n) で済みます。各要素は一度しか参照されないためです。

実装コード

const arr1 = [23, 67, 789];
const arr2 = [23, 789, 67];
const sourceArr = [[23], [789, 67]];

const validFormation = (arr, sourceArr) => {
  // 各サブ配列の先頭要素をキーに、サブ配列の位置を記録したマップを作成
  const indexes = new Map();
  sourceArr.forEach((sub, i) => indexes.set(sub[0], i));

  let arrIndex = 0;

  // ターゲット配列を先頭から順に照合していく
  while (arrIndex < arr.length) {
    const index = indexes.get(arr[arrIndex]);
    if (index === undefined) return false; // 先頭が一致するサブ配列が存在しない

    const sub = sourceArr[index];
    for (let j = 0; j < sub.length; ++j) {
      if (arr[arrIndex] !== sub[j]) return false; // 要素の並びが不一致
      ++arrIndex;
    }
  }
  return true;
};

console.log(validFormation(arr1, sourceArr));
console.log(validFormation(arr2, sourceArr));

出力

上記のコードを実行すると、次の出力が得られます。

false
true

arr1 はサブ配列内の順序制約のため形成できませんが、arr2 は [23] と [789, 67] をこの順に連結すれば再現できるため、true となります。