JavaScriptで正方行列の要素をスパイラル順に取得する方法

はじめに

本記事では、二次元配列（必ず正方行列であるもの）を引数として受け取り、その要素をスパイラル（渦巻き）状に取り出して1次元配列として返すJavaScript関数の実装方法を解説します。

まず、対象となる配列は以下のような形式です。

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

関数は位置(0, 0)からスタートし、外周に沿って時計回りに要素を取り出していきます。上記の配列の場合、期待される出力は次のとおりです。

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

アルゴリズムの考え方

この問題は、「現在の行と列」を指す一時的な変数を、開始位置と終了位置のそれぞれに対して用意することでエレガントに解決できます。

各ループのたびに開始行・開始列を1つずつ増やし、終了行・終了列を1つずつ減らしていくことで、行列の中心へ向かって螺旋状に走査範囲を狭めていきます。

1周あたりの処理は、以下の4ステップで構成されます。

1. 左 → 右： 開始行の要素を先頭から末尾まで追加し、開始行を1つ進める
2. 上 → 下： 終了列の要素を上から下まで追加し、終了列を1つ減らす
3. 右 → 左： 終了行の要素を末尾から先頭まで追加し、終了行を1つ減らす
4. 下 → 上： 開始列の要素を下から上まで追加し、開始列を1つ進める

なお、行または列が残り1つしかない場合に同じ要素が二重に追加されてしまうのを防ぐため、「右 → 左」と「下 → 上」の処理には条件分岐が必要になる点に注意してください。

実装例

const arr = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ];
const spiral = (arr = []) => {
    if (!arr || arr.length === 0) {
        return [];
    };
    let startRow = 0;
    let startCol = 0;
    let res = [];
    let endCol = arr[0].length - 1;
    let endRow = arr.length - 1;
    while (startRow <= endRow && startCol <= endCol) {
        for (let i = startCol; i <= endCol; i++) {
            res.push(arr[startRow][i]);
        }
        startRow++;
        for (let i = startRow; i <= endRow; i++) {
            res.push(arr[i][endCol]);
        }
        endCol--;
        if (startRow <= endRow) {
            for (let i = endCol; i >= startCol; i--) {
                res.push(arr[endRow][i]);
            }
            endRow--;
        }
        if (startCol <= endCol) {
            for (let i = endRow; i >= startRow; i--) {
                res.push(arr[i][startCol]);
            } startCol++;
        }
    }
    return res;
};
console.log(spiral(arr));

出力結果

コンソールに出力される結果は以下のとおりです。

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

まとめ

開始行・開始列・終了行・終了列の4つの境界変数を管理しながら、外周を1周ごとに内側へ狭めていくことで、正方行列をスパイラル順に走査できます。要素数をn×nとした場合の時間計算量はO(n²)、出力用の配列を除けば追加のメモリはほぼ不要で、非常に効率的なアプローチです。