Pythonで行列内の「ラッキーナンバー」(行と列の両方で最大の数)を数える方法

問題の概要

ある行列(マトリックス)が与えられたとき、「その行においても、その列においても最も大きい値になっている整数」がいくつあるかを求める問題です。このような数字は「ラッキーナンバー(Lucky Number)」とも呼ばれます。

例として、次のような入力を考えてみましょう。

この場合、答えは 2 になります。条件を満たすのは 6 と 7 の2つだけだからです。

• 6: 2行目(4, 6, 5)の最大値であり、同時に2列目(3, 6, 5)の最大値でもある
• 7: 3行目(1, 5, 7)の最大値であり、同時に3列目(2, 5, 7)の最大値でもある

解き方のアプローチ

この問題は、以下の手順で効率よく解くことができます。

1. 各行の最大値をまとめたリスト r_maxes を作成する。
2. 各列の最大値をまとめたリスト c_maxes を作成する。
3. すべてのセルを走査し、その値が「行の最大値」かつ「列の最大値」と一致する場合に、結果リストへ追加する。
4. 最後に、結果リストの要素数を返す。

実装例(Python)

class Solution:
    def solve(self, matrix):
        mat = matrix
        trans_mat = list(zip(*matrix))
        print(mat, trans_mat)
        r_maxes = [max(row) for row in mat]
        c_maxes = [max(t_row) for t_row in trans_mat]
        a = []
        for r in range(len(mat)):
            for c in range(len(trans_mat)):
                v = mat[r][c]
                if (r_maxes[r], c_maxes[c]) == (v, v):
                    a.append(v)
        return len(a)

ob = Solution()
matrix = [
    [1, 3, 2],
    [4, 6, 5],
    [1, 5, 7]
]
print(ob.solve(matrix))

入力

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

出力

2

コードのポイント

転置行列で列を簡単に扱う

Pythonでは zip(*matrix) を使うことで、行列をワンラインで転置できます。これにより「列ごとの最大値」も、行の場合とまったく同じように max() で求められるのが大きなポイントです。

計算量

• 時間計算量: O(m × n)(m:行数、n:列数)— 全セルを一度ずつ確認します。
• 空間計算量: O(m + n)— 行・列それぞれの最大値リストを保持します。

シンプルながら効率的なこの手法は、競技プログラミングやコーディング面接で頻出の定番パターンです。ぜひ覚えておきましょう。