Pythonで2次元バイナリ行列の最も左にある「1」の列インデックスを効率的に求める方法

問題の概要

2次元のバイナリ行列（0と1のみで構成される行列）が与えられます。ここで、各行は昇順にソートされており、すべての0が1よりも先に並んでいるものとします。この条件のもとで、行列全体の中で最も左側に存在する「1」の列インデックスを見つけるプログラムを作成します。該当する「1」が存在しない場合は -1 を返します。

例えば、次のような入力が与えられたとします。

この場合、出力は 2 となります。なぜなら、3列目（インデックス2）に、行列全体で最も左に位置する「1」が存在するからです。

解法のアプローチ

この問題は、右上の角から探索を開始し、条件に応じて左または下へ移動するという効率的な手法で解くことができます。各行がソート済みであるという性質を利用することで、全要素を走査する必要がなくなります。

具体的な手順は以下の通りです。

• 行列が空の場合は、-1 を返します。
• N を行数、M を列数とします。
• 探索位置 i = 0（先頭行）、j = M - 1（最終列）からスタートします。
• 答えを格納する変数 leftmost を -1 で初期化します。
• i < N かつ j >= 0 の間、以下を繰り返します。
  • matrix[i][j] が 0 の場合：その行にはそれより右に「1」しか存在しないため、下の行へ移動します（i += 1）。
  • matrix[i][j] が 1 の場合：これが現在わかっている中で最も左の「1」なので、leftmost を j で更新し、さらに左へ移動します（j -= 1）。
• ループ終了後、leftmost の値を返します。

このアルゴリズムの計算量は O(N + M) であり、行列のサイズに対して非常に効率的です。各ステップで必ず行または列のどちらかが減少していくためです。

実装例（Pythonコード）

class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return -1

        N = len(matrix)
        M = len(matrix[0])

        i = 0
        j = M - 1

        leftmost = -1

        while i < N and j >= 0:
            if matrix[i][j] == 0:
                i += 1
            else:
                leftmost = j
                j -= 1

        return leftmost

ob = Solution()
matrix = [
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(ob.solve(matrix))

入力

[
[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 0, 1, 1],
[0, 0, 1, 0] ]

出力

2

まとめ

ソート済みバイナリ行列の特性を活かしたこの手法では、右上からスタートして「0なら下へ、1なら左へ」と移動するだけで、最短 O(N + M) の時間で答えを導き出せます。全マスを走査する O(N × M) の素朴な方法と比べ、大規模な行列でも高速に動作する点が大きなメリットです。