JavaScriptで行列の対角線がすべて同じ要素かどうかを判定する方法

問題概要

リテラルを要素とする2次元配列 arr を第一引数（唯一の引数）として受け取るJavaScript関数を作成します。

この関数の役割は、行列の左上から右下へ向かうすべての対角線が同じ要素で構成されているかどうかを判定することです。これは、いわゆる「トゥーマトリックス（Toeplitz行列）」と呼ばれる行列の判定問題に相当します。

条件を満たしていれば true を、そうでなければ false を返します。

例として、次の入力を関数に渡した場合を考えてみましょう。

入力

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

出力

const output = true;

出力の解説

上記の配列における対角線は次のとおりです。

[1], [2,2], [6,6,6], [7,7,7], [8,8], [9]

すべての対角線において要素が同一であるため、結果は true となります。

実装例

以下が実際のコードです。

const arr = [
    [6, 7, 8, 9],
    [2, 6, 7, 8],
    [1, 2, 6, 7],
];
const checkMatrix = (arr = []) => {
    const validate = (row, col) => {
        while (
            row < arr.length
            && col < arr[0].length
            && arr[row + 1]
            && arr[row + 1][col + 1] !== undefined
        ) {
            if (arr[row + 1][col + 1] !== arr[row][col]) {
                return false
            }
            row += 1
            col += 1
        }
        return true
    }
    for (let i = 0; i < arr[0].length; i++) {
        if (!validate(0, i)) {
            return false
        }
    }
    for (let i = 0; i < arr.length; i++) {
        if (!validate(i, 0)) {
            return false
        }
    }
    return true
}
console.log(checkMatrix(arr));

出力結果

true

コードの解説

この実装のポイントは以下のとおりです。

• validate関数：指定された開始位置（row, col）から右下方向へ対角線をたどり、隣接する要素が一致しない場合は即座に false を返します。
• 1行目のチェック：最初のループでは、1行目の各列を起点として対角線を検証します。
• 1列目のチェック：次のループでは、1列目の各行を起点として対角線を検証します。これにより、すべての対角線を漏れなくカバーできます。
• 計算量：行列のサイズを m × n とすると、時間計算量は O(m × n)、各マスを高々1回しか訪問しないため効率的です。

このように、各対角線の起点を順番に走査しながら隣接要素の一致を確認するだけで、シンプルかつ効率的にトゥーマトリックスの判定が実現できます。