JavaScriptで正方行列を斜めに走査する方法

問題

行数と列数が同じ「正方行列」（配列の中に配列が入った構造）を受け取り、それを対角線に沿って斜めに走査し、出会った順番どおりに要素を並べた新しい配列を作成するJavaScript関数を実装します。

例えば、関数への入力が以下のとおりだったとします。

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

この場合、出力として期待されるのは次の配列です。

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

つまり、左上からスタートし、対角線ごとに要素を拾いながら、向きを交互に切り替える（ジグザグに進む）ことで要素を並べ替えます。1本目の対角線は右上方向、2本目は左下方向、というように交互にたどっていくイメージです。

コード例

この問題を解くコードは以下のとおりです。

const arr = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const findDiagonalOrder = (arr = []) => {
    if(!arr.length){
       return [];
    };
    let ind = 0;
    let colBegin = 0, rowBegin = 0;
    let rowMax = arr.length, colMax = arr[0].length;
    const res = [], stack = [];
    while(rowBegin< rowMax || colBegin<colMax) {
       for(let row = rowBegin, col = colBegin; row < rowMax && col >=0 ;
       row++,col--){
          if(ind%2 === 0){
             stack.push((arr[row][col]));
          }else{
             res.push(arr[row][col]);
          };
       };
       ind++;
       while(stack.length){
          res.push(stack.pop());
       };
       colBegin++
       if(colBegin> colMax-1 && rowBegin < rowMax){
          colBegin = colMax-1
          rowBegin++
       }
   };
   return res
};
console.log(findDiagonalOrder(arr));

コードの解説

この実装では、以下の手順で処理を進めています。

• 走査の起点となる位置を記録しながら、一定の方向に沿って要素をたどります。

• 対角線の番号（インデックス）が偶数の場合は、いったんスタックに要素をプッシュし、その対角線の端に達した時点でポップして出力用の配列へ追加します。これにより、対角線上の要素が逆順に並びます。

• 次の対角線へ移るたびにインデックスをインクリメントし、走査の向きを切り替えます。

• 列の開始インデックスは末尾に達するまで増加し続けます。末尾に到達した後は、列の開始位置を最終列に固定したまま、代わりに行の開始インデックスを増やしていきます。

なお、このアルゴリズムの時間計算量は O(n × m)（nは行数、mは列数）、空間計算量も出力配列とスタックのため O(n × m) となります。すべての要素をちょうど一度ずつ訪れるため、効率的な解法と言えます。

出力結果

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

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