JavaScriptで配列のネストされた集合の最長の長さを見つけて返す方法

問題

数値の配列 arr を第一引数（かつ唯一の引数）として受け取るJavaScript関数を作成する必要があります。

長さ N の配列 arr には、0 から N-1 までのすべての整数がちょうど1回ずつ含まれています。この関数では、次のルールに従って構成される集合 S の最長の長さを見つけ、その結果を返す必要があります。ここで、S[i] = {A[i], A[A[i]], A[A[A[i]]], ...} と定義されます。

具体的には、S の最初の要素としてインデックス i の要素 A[i] を選択することから始め、次の要素は A[A[i]]、その次は A[A[A[i]]]… というように順に辿っていきます。そして、S の中に重複する要素が現れる直前で追加を停止します。

例えば、関数への入力が次の場合 −

const arr = [5, 4, 0, 3, 1, 6, 2];

出力は次のようになります −

const output = 4;

出力の説明

各要素の値は以下のとおりです。

A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2

このとき、最も長い S[K] の一つは次のようになります。

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

インデックス 0 → 5 → 6 → 2 → 0 と辿ると元の位置に戻るため、重複が発生する直前の要素数である「4」が答えとなります。

アプローチ

この問題は、各インデックスから順に値をたどりながらサイクル（一周して戻ってくる経路）の長さを数えることで解決できます。すでに訪問済みのインデックスは再度調べる必要がないため、visited オブジェクトで管理することで計算量を大幅に削減できます。全体の計算量は O(N) です。

例

以下が実際のコードです −

const arr = [5, 4, 0, 3, 1, 6, 2];

const arrayNesting = (arr = []) => {
   // 訪問済みのインデックスを記録するオブジェクト
   const visited = {};

   // 指定インデックスから辿れる連鎖の長さを再帰的に求める
   const aux = (index) => {
      if (visited[index]) {
         return 0;
      }
      visited[index] = true;
      return aux(arr[index]) + 1;
   };

   let max = 0;
   arr.forEach((n, index) => {
      if (!visited[index]) {
         max = Math.max(max, aux(index));
      }
   });

   return max;
};

console.log(arrayNesting(arr));

コードの説明

• visited：一度チェックしたインデックスを記録し、同じ経路を二度以上探索しないためのフラグです。
• aux(index)：指定したインデックスから A[i] → A[A[i]] → … と再帰的に値をたどり、連鎖の長さを返します。訪問済みなら 0 を返します。
• forEach：まだ訪問していないインデックスを起点として aux を呼び出し、最大値を更新していきます。

出力

コンソールには次のように出力されます −

4