BFE.devでのAI解答例 - JavaScript コーディング問題
138. ソート済みの配列の共通要素

解答例：

function intersect(arr1, arr2) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++;
      j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

時間コストはO(n+m)であり、nとmはそれぞれ配列の長さです。配列がソートされているので配列の要素を一つずつ比較し、共通要素であれば結果配列に追加し、ポインタを進めます。

空間コストは、結果配列を用意するためにO(k)であり、kは共通要素の数です。最悪の場合、配列の要素が全て共通している場合、kは配列の長さの少ない方に等しくなる。

改善する余地は、配列の長さが巨大な場合には並列処理を考慮することができます。また、配列の長さが小さい場合には単純な線形探索でも対応できる場合があります。