JavaScriptでインデックスの合計が最小となる共通要素を見つける方法

問題概要

2つの配列 arr1 と arr2 を引数として受け取るJavaScriptの関数を作成します。

この関数の目的は、両方の配列に共通して存在する要素のうち、各配列におけるインデックスの合計（リストインデックスサム）が最小になる要素を見つけ出すことです。条件を満たす要素が複数ある場合は、順序を問わずすべてを出力します。

入力例

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];

出力例

const output = ['a'];

出力の解説

両方の配列に共通する要素は「d」と「a」です。それぞれのインデックスの合計を計算すると、

• 「d」の場合：arr1でのインデックス3 + arr2でのインデックス0 = 3
• 「a」の場合：arr1でのインデックス0 + arr2でのインデックス1 = 1

合計が最小なのは「a」であるため、答えは ['a'] となります。

アルゴリズムの考え方

効率的に解くには、ハッシュマップ（オブジェクト）を活用します。手順は以下のとおりです。

1. まず、arr1 の各要素とそのインデックスをマップに登録します。
2. 次に arr2 を走査し、共通する要素について「arr1でのインデックス + arr2でのインデックス」を計算します。
3. その合計が現在の最小値より小さければ最小値を更新します。
4. 最後に、もう一度 arr2 を走査し、合計が最小値と一致する要素をすべて結果配列に追加します。

この方法により、時間計算量は O(n + m) で処理できます（n と m はそれぞれの配列の長さ）。

実装コード

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];

const findCommon = (arr1 = [], arr2 = []) => {
  let sum = Infinity;
  // arr1 の要素とインデックスをマップに登録
  const map = arr1.reduce((acc, str, index) => {
    acc[str] = index;
    return acc;
  }, {});
  // 最小のインデックス合計を求める
  for (let i = 0; i < arr2.length; i++) {
    const index1 = map[arr2[i]];
    if (index1 >= 0 && index1 + i < sum) {
      sum = index1 + i;
    }
  }
  // 最小合計に一致する要素をすべて収集
  const result = [];
  for (let i = 0; i < arr2.length; i++) {
    const index1 = map[arr2[i]];
    if (index1 >= 0 && index1 + i === sum) {
      result.push(arr2[i]);
    }
  }
  return result;
};

console.log(findCommon(arr1, arr2));

実行結果

['a']

まとめ

本記事では、2つの配列からインデックスの合計が最小の共通要素を求める方法を紹介しました。ポイントは以下の3つです。

• reduce() を使って arr1 の要素をキー、インデックスを値とするマップを構築することで、要素検索を O(1) に高速化できる
• 最初のループで最小のインデックス合計を特定し、2回目のループで該当する要素をすべて集めるという2段階のアプローチを採ることで、同点の要素にも正しく対応できる
• 全体の計算量は O(n + m) となり、入れ子のループを使う O(n × m) の素朴な実装よりも効率的

同様の問題はLeetCodeの「Minimum Index Sum of Two Lists」などでも出題される定番テーマなので、ぜひマップを使った解法パターンを身につけておきましょう。