JavaScriptで正方行列を90度回転させる方法｜追加メモリ不要のin-place実装

n × n の二次元配列（正方行列）を受け取り、それを時計回りに90度回転させるJavaScript関数を作成してみましょう。

ここでの重要な条件は、余分な配列を新しく確保せずに（in-placeで）処理を行うことです。つまり、元の配列そのものを直接書き換えて回転を実現します。

入力例と期待される出力

たとえば、次のような3×3の行列が入力だった場合を考えます。

const arr = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

この行列を時計回りに90度回転すると、結果は次のようになります。

const output = [
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3],
];

回転の考え方：転置＋行の反転

正方行列を時計回りに90度回転するには、以下の2ステップが有効です。

手順1：行列を転置する
行と列を入れ替えます。具体的には、要素 arr[i][j] と arr[j][i] を交換します。対角線より上側だけを走査すれば十分なので、内側のループは j = i + 1 から開始します。

手順2：各行を左右に反転する
転置後の各行について、左端と右端の要素を順に交換していきます。各行の中央まで処理できればよいので、内側のループは arr.length / 2 まで走査します。

この2つの操作を組み合わせることで、追加の配列を一切使わずに回転が完了します。

実装コード

要素の交換には、ES2015以降で使える分割代入（デストラクチャリング）によるスワップを利用しています。これにより一時変数を用意せずに済み、コードもすっきりします。

const arr = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

const rotateArray = (arr = []) => {
    // 手順1：行列を転置する（行と列を入れ替え）
    for (let rowIndex = 0; rowIndex < arr.length; rowIndex += 1) {
        for (let columnIndex = rowIndex + 1; columnIndex < arr.length;
        columnIndex += 1) {
            [
                arr[columnIndex][rowIndex],
                arr[rowIndex][columnIndex],
            ] = [
                arr[rowIndex][columnIndex],
                arr[columnIndex][rowIndex],
            ];
        }
    }

    // 手順2：各行を左右反転する
    for (let rowIndex = 0; rowIndex < arr.length; rowIndex += 1) {
        for (let columnIndex = 0; columnIndex < arr.length / 2;
        columnIndex += 1) {
            [
                arr[rowIndex][arr.length - columnIndex - 1],
                arr[rowIndex][columnIndex],
            ] = [
                arr[rowIndex][columnIndex],
                arr[rowIndex][arr.length - columnIndex - 1],
            ];
        }
    }
};

rotateArray(arr);
console.log(arr);

実行結果

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

[ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]

計算量について

このアルゴリズムの時間計算量は O(n²) です。行列のすべての要素を定数回ずつ訪問するため、これ以上効率化することはできません。また、追加の配列を確保しないため空間計算量は O(1) となり、「in-placeで回転せよ」という条件を満たしています。