JavaScriptで昇順ソートされた3つの配列の共通要素（積集合）を効率的に求める方法

はじめに

本記事では、JavaScriptを使って「昇順にソートされた3つの整数配列」を受け取り、その3つすべてに存在する要素だけを抽出した新しい配列を構築して返す関数の実装方法を解説します。

配列がそれぞれソート済みであるという前提を活かせば、全件を比較する非効率な方法ではなく、3つのポインタ（インデックス）を同時に進めていく三方向マージ的な手法で、線形時間 O(n) で共通要素を見つけることができます。

問題の概要

要件は以下のとおりです。

• 引数として、昇順にソートされた整数の配列を3つ受け取る
• 3つの配列すべてに出現する要素のみを含む配列を返す

入力例

const arr1 = [4, 7, 8, 11, 13, 15, 17];
const arr2 = [1, 3, 4, 13, 18];
const arr3 = [2, 4, 7, 8, 9, 10, 13];

期待される出力

この場合、3つの配列すべてに共通して存在するのは 4 と 13 の2つなので、出力は次のようになります。

const output = [4, 13];

実装コード

それでは、実際のコードを見ていきましょう。各配列に対して1つずつポインタを用意し、値を比較しながら進めるシンプルなアプローチです。

const arr1 = [4, 7, 8, 11, 13, 15, 17];
const arr2 = [1, 3, 4, 13, 18];
const arr3 = [2, 4, 7, 8, 9, 10, 13];

const intersectThree = (arr1 = [], arr2 = [], arr3 = []) => {
    // 各配列の現在位置を示すポインタを初期化
    let curr1 = 0;
    let curr2 = 0;
    let curr3 = 0;
    const res = [];

    // どれか1つの配列でも末尾に達したらループ終了
    while ((curr1 < arr1.length) && (curr2 < arr2.length) && (curr3 < arr3.length)) {
        // 3つの配列の現在位置の値がすべて一致すれば共通要素
        if ((arr1[curr1] === arr2[curr2]) && (arr2[curr2] === arr3[curr3])) {
            res.push(arr1[curr1]);
            curr1++;
            curr2++;
            curr3++;
        }

        // 最も大きい値より小さいポインタだけを前に進める
        const max = Math.max(arr1[curr1], arr2[curr2], arr3[curr3]);
        if (arr1[curr1] < max) {
            curr1++;
        }
        if (arr2[curr2] < max) {
            curr2++;
        }
        if (arr3[curr3] < max) {
            curr3++;
        }
    }
    return res;
};

console.log(intersectThree(arr1, arr2, arr3));

コードの解説

このアルゴリズムのポイントは以下の2点です。

1. 一致判定： 3つの配列の現在位置にある値が完全に一致した場合、それは共通要素なので結果配列 res に追加し、3つのポインタをすべて1つ進めます。
2. ポインタの前進： 一致しなかった場合は、3つの値の中で最も大きい値（max）より小さい値を持つ配列のポインタだけを進めます。これは、ソート済み配列では「それより小さい値が後から現れることはない」ため、その値が他の配列と一致する可能性を排除できるからです。

この仕組みにより、各配列を一度だけ走査すればよく、計算量は O(n₁ + n₂ + n₃)、空間計算量は出力を除けば O(1) で済みます。

実行結果

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

[4, 13]

まとめ

ソート済みの複数配列から共通要素を求める場合、filter や includes を組み合わせる方法もありますが、計算量が O(n × m) になってしまいます。今回紹介したように複数ポインタを同時に操作する手法を使えば、ソート済みであることを最大限に活かし、線形時間で処理できる点が大きなメリットです。同様のアプローチは、2つの配列の積集合や差分抽出などにも応用できるので、ぜひ覚えておきましょう。