JavaScriptでマトリックス（行列）内のラッキーナンバーを見つける方法

すべての要素が互いに異なる m × n 行列が与えられたとき、その中にある「ラッキーナンバー」をすべて見つけて返すのが今回の課題です。

ラッキーナンバーとは、自分の属する行の中で最小値であり、かつ自分の属する列の中で最大値である要素のことを指します。

具体例

たとえば、次のような入力配列を考えてみましょう。

const arr = [
    [3,7,8],
    [9,11,13],
    [15,16,17]
];

この場合の出力は次のようになります。

const output = [15];

これは、15 が最下行の中で最小の値であり、同時に第1列の中で最大の値でもあるため、この行列における唯一のラッキーナンバーだからです。

解法のコード

const arr = [
    [3,7,8],
    [9,11,13],
    [15,16,17]
];
const luckyNumbers = (arr, res = []) => {
    const M = arr.length, N = arr[0].length;
    // 各行の最小値を保持する配列
    const min = Array(M).fill(Infinity);
    // 各列の最大値を保持する配列
    const max = Array(N).fill(-Infinity);
    // 全要素を一度だけ走査して最小値・最大値を更新
    for (let i = 0; i < M; ++i)
        for (let j = 0; j < N; ++j)
            min[i] = Math.min(min[i], arr[i][j]),
            max[j] = Math.max(max[j], arr[i][j]);
    // 行の最小値と列の最大値が一致する要素を収集
    for (let i = 0; i < M; ++i)
        for (let j = 0; j < N; ++j)
            if (min[i] === max[j])
                res.push(arr[i][j]);
    return res;
};
console.log(luckyNumbers(arr));

コードのポイント

このアルゴリズムの肝は、行列全体をあらかじめ走査しておき、各行の最小値を格納した配列 min と、各列の最大値を格納した配列 max を作成することです。

その後にもう一度行列を走査し、min[i] と max[j] が一致する位置 (i, j) の要素こそが、「行内で最小・列内で最大」という条件を満たすラッキーナンバーとなります。

なお、すべての数値が互いに異なるという前提があるため、ラッキーナンバーは高々1個しか存在しないという性質もあります。

計算量

• 時間計算量：O(M × N) — 行列の全要素を最大2回走査するため
• 空間計算量：O(M + N) — 行ごとの最小値と列ごとの最大値を保存するため

出力結果

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

[15]