JavaScriptでソート済み配列の各要素の二乗を昇順に求める方法

問題

昇順にソートされた整数の配列 arr を引数として受け取るJavaScript関数を作成する必要があります。

この関数は、各数値の二乗を計算し、それらも昇順に並べ替えた配列として返さなければなりません。

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

const arr = [-2, -1, 1, 3, 6, 8];

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

const output = [1, 1, 4, 9, 36, 64];

解法のポイント：二ポインタ法

この問題は二ポインタ（Two Pointers）と呼ばれる手法を使うと効率的に解けます。元の配列が昇順にソートされているため、負の数でも絶対値が大きいほど二乗した値は大きくなります。そこで、配列の左端と右端の2つのポインタを用意し、それぞれの位置にある数値の二乗を比較して、大きい方から結果配列に追加していきます。最後に結果を反転すれば、昇順に並んだ二乗の配列が完成します。

このアプローチの計算量は O(n) です。すべての要素を二乗してから改めてソートする方法（O(n log n)）よりも高速で、ソート済みという前提条件を最大限に活かした解法と言えます。

コード例

実装コードは以下の通りです −

const arr = [-2, -1, 1, 3, 6, 8];
const findSquares = (arr = []) => {
   const res = []
   let left = 0
   let right = arr.length - 1
   while (left <= right) {
      const leftSquare = arr[left] * arr[left]
      const rightSquare = arr[right] * arr[right]
      if (leftSquare < rightSquare) {
         res.push(rightSquare)
         right -= 1
      } else {
         res.push(leftSquare)
         left += 1
    }
   }
   return res.reverse();
};
console.log(findSquares(arr));

処理の流れ

1. ポインタ left を先頭、right を末尾に配置します。
2. 両端の要素をそれぞれ二乗し、大きい方を結果配列 res の後ろに追加します。
3. 追加した側のポインタを内側へ移動させ、left が right を追い越すまで繰り返します。
4. 最後に res.reverse() で反転すると、昇順にソートされた二乗の配列が得られます。

出力

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

[ 1, 1, 4, 9, 36, 64 ]