JavaScriptでマトリックス内のラッキーナンバーをすべて見つける方法

ラッキーナンバーとは？

「ラッキーナンバー」とは、行列（マトリックス）の中で、自分の行における最小値であり、同時に自分の列における最大値でもある要素のことを指します。

今回の課題は、整数の二次元配列を受け取るJavaScript関数を書くことです。この関数は、配列内に存在するすべてのラッキーナンバーを見つけ出し、新しい配列として返します。条件を満たす要素がひとつも存在しない場合は、空の配列を返します。

入力例と出力例

たとえば、次のような二次元配列が与えられたとしましょう。

const arr = [
    [5, 3, 7, 3],
    [4, 2, 67, 2],
    [2, 32, 7, 4],
    [2, 9, 45, 23]
];

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

const output = [];

このマトリックスには「行で最小かつ列で最大」という条件を満たす要素が存在しないため、結果は空の配列となります。

解き方のアプローチ

この問題を効率よく解くには、次の手順で考えます。

• ステップ1：各列ごとの最大値をあらかじめ計算しておく。
• ステップ2：各行の最小値を求める。
• ステップ3：行の最小値が、その要素のある列の最大値と一致していれば、それはラッキーナンバー。結果の配列に追加する。
• ステップ4：すべての行を調べ終えたら、結果の配列を返す。

コード例

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

const arr = [
    [5, 3, 7, 3],
    [4, 2, 67, 2],
    [2, 32, 7, 4],
    [2, 9, 45, 23]
];
const luckyNumbers = (arr = []) => {
    const rows = arr.length;
    const cols = arr[0].length;

    // 各列の最大値を事前に計算しておく
    const colMax = [];
    for (let j = 0; j < cols; j++) {
        let max = -Infinity;
        for (let i = 0; i < rows; i++) {
            max = Math.max(max, arr[i][j]);
        }
        colMax.push(max);
    }

    // 行の最小値が、その列の最大値と一致するかをチェック
    const result = [];
    for (let i = 0; i < rows; i++) {
        const minRow = Math.min(...arr[i]);
        const pos = arr[i].indexOf(minRow);
        if (minRow === colMax[pos]) {
            result.push(minRow);
        }
    }
    return result;
};
console.log(luckyNumbers(arr));

実行結果

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

[]

コードの解説

ここからは、コードのポイントを順番に見ていきましょう。

1. 各列の最大値を事前に計算

最初の二重ループでは、各列 j に対して、その列に含まれる全要素の中から最大値を求め、colMax 配列に格納しています。こうすることで、後の判定処理のたびに列を何度も走査し直す必要がなくなります。

2. 行の最小値とその位置を特定

Math.min(...arr[i]) ではスプレッド構文を使って各行の最小値を取得し、indexOf() によってその最小値が何番目の列に位置するかを特定しています。

3. ラッキーナンバーの判定

行の最小値 minRow が、同じ列位置の最大値 colMax[pos] と一致すれば、その要素は「行で最小・列で最大」を同時に満たしているため、ラッキーナンバーとして結果に追加されます。

計算量について

この実装の時間計算量は O(m × n)（m は行数、n は列数）です。各要素の参照は高々2回程度で済むため、大きなマトリックスでも効率的に動作します。また、複数のラッキーナンバーが存在する場合にも、すべてを正しく収集して返せる点がこの実装の強みです。