JavaScriptの配列で特別な条件を満たす要素ペアを見つける方法

課題の概要

JavaScriptでは、次の3つの引数を受け取る関数を作成する課題があります。

arr → 整数の配列
m   → 正の整数
n   → 正の整数

この関数の目的は、配列内に次の両方の条件を満たす2つの要素(a1・a2と呼びます)が存在するかどうかを判定することです。

• 値の条件: a1とa2の値の絶対差がn以内であること
• 位置の条件: a1とa2のインデックス(添字)の絶対差がm以内であること

言い換えれば、「値が近く、かつ配列上の位置も近いペア」が存在するかを調べる処理です。この種の問題は、一定範囲内にある近接重複(nearby duplicate)を検出する問題としてよく知られています。

アプローチ: ソート+ツーポインタで効率化する

すべての組み合わせを総当たりで調べることも可能ですが、その場合の計算量はO(N²)となり、配列が大きくなると実用性を欠きます。

そこで有効なのが、次の3ステップからなる手法です。

1. 各要素を「値」と「元のインデックス」を持つオブジェクトに変換する
2. 値を基準に昇順ソートする
3. ソート後の配列に対してleft・rightの2つのポインタを動かしながら、条件を満たすペアを探す

値でソートしておけば、値の差が広がりすぎたときにleftを進め、インデックスの差が広がりすぎたときにrightを進めるという判断ができるため、無駄な比較を大幅に減らすことができます。

サンプルコード

const arr = [1, 2, 3, 1, 7, 8];

const findSpecialElements = (arr = [], m, n) => {
  const map = arr
    .map((el, ind) => ({ el, ind }))
    .sort((a, b) => a.el - b.el);

  let left = 0;
  let right = 1;

  while (right < map.length) {
    const diff = Math.abs(map[right].el - map[left].el);
    const range = Math.abs(map[right].ind - map[left].ind);

    if (diff <= n && range <= m) {
      return true;
    } else if (diff > n) {
      left++;
    } else if (range > m) {
      right++;
    }

    if (left === right) {
      right++;
    }
  }
  return false;
};

console.log(findSpecialElements(arr, 3, 0));

実行結果

true

出力がtrueになる理由

サンプルではfindSpecialElements(arr, 3, 0)として呼び出しています。配列[1, 2, 3, 1, 7, 8]には、値「1」がインデックス0と3の2か所に存在します。この2つの要素について確認すると、

• 値の絶対差: |1 − 1| = 0 → n = 0 の条件を満たす
• インデックスの絶対差: |3 − 0| = 3 → m = 3 の条件を満たす

となり、両方の条件を同時に満たすペアが存在するため、関数はtrueを返します。

コードのポイント解説

• map()+sort(): 各要素を{ el, ind }の形式に変換してから値でソートしています。元の位置情報を失わないよう、インデックスをセットで保持しておくのが重要なポイントです。
• diff(値の差): leftとrightが指す要素の値の絶対差です。nより大きい場合はleftを進めて値の差を縮めます。
• range(インデックスの差): 元の配列における2要素の位置の絶対差です。mより大きい場合はrightを進めて次の候補へ移ります。
• left === right のガード処理: ポインタが重なると同じ要素同士を比較してしまうため、rightを1つ進めて回避しています。

計算量

• 時間計算量: O(N log N) … ソートがボトルネックとなり、その後のポインタ走査は線形時間で完了します
• 空間計算量: O(N) … 値とインデックスのペアを格納するために必要です

総当たり法のO(N²)と比較すると大幅に高速化できるため、要素数の多い配列を扱う場合でも実用的なアプローチといえます。