Pythonで行列の全行に共通する最小値を見つけるプログラム

問題の概要

各行が昇順にソートされた2次元行列（マトリックス）が与えられたとします。このとき、すべての行に共通して存在する最小の数を見つける必要があります。共通する要素が1つも存在しない場合は、-1 を返します。

例えば、以下のような入力があったとします。

この場合、3つの行すべてに存在する数は「5」だけなので、出力は 5 となります。

解決のアプローチ

この問題は、Pythonの集合（set）の積集合を利用することで、シンプルかつ効率的に解くことができます。具体的な手順は以下の通りです。

• 行列が空の場合は、-1 を返します。
• 最初の行の要素から集合を作成します。
• 行列の各行について、現在の集合とその行の要素から作った集合との積集合を求めます。
• 途中で積集合が空になった場合は、共通要素が存在しないことが確定するため、-1 を返して処理を終了します。
• すべての行の処理が終わったら、残った集合の中の最小値を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        first = set(matrix[0])
        for row in matrix:
            first &= set(row)
            if not first:
                return -1
        return min(first)

ob1 = Solution()
matrix = [
    [2, 3, 5],
    [5, 10, 10],
    [1, 3, 5]
]
print(ob1.solve(matrix))

入力

matrix = [
[2, 3, 5],
[5, 10, 10],
[1, 3, 5]
]

出力

5

コードのポイントと計算量

この実装では、&= 演算子を使って集合の積集合を簡潔に計算しています。各行を処理するたびに共通要素が絞り込まれていくため、早期に空集合になった場合は即座に -1 を返すことで無駄な計算を避けられます。

時間計算量は O(n × m) です。ここで n は行数、m は1行あたりの要素数を表します。また、各行が昇順にソートされているという条件を活かせば、二分探索を用いるなどの別のアプローチも考えられますが、集合を使うこの方法はコードが短く直感的で、実用性の高い実装と言えます。