【Python】列の入れ替えが許されたバイナリ行列で、1だけで構成される最大長方形を求める方法

問題の概要

0と1だけで構成されるバイナリ行列が与えられます。この中から「すべて1で埋まった最大の長方形」を見つけ、その面積を求めるのが本記事のテーマです。ポイントは、任意の2つの列を入れ替えてよいという条件がある点です。

例として、次の行列を見てみましょう。

この場合、答えは 6 です。1列目と3列目を入れ替えると、次のように3列目と4列目がすべて1になり、高さ3・幅2の長方形(面積 3 × 2 = 6)が現れます。

解法の考え方

列を自由に入れ替えられるということは、ある行を底辺としたとき、その行の各列の「高さ」を好きな順番に並べ替えられることを意味します。この性質を利用すると、次の手順で問題を解けます。

1. 高さの前計算: 各マスについて、同じ列を上方向にたどって連続して並ぶ1の個数(ヒストグラムの高さ)を求めます。マスが0なら高さは0、1なら直上のマスの高さ+1となります。
2. 降順ソート: 各行の高さのリストを降順にソートします。これが「列の入れ替え」に相当し、高い列ほど左側に集まることになります。
3. 面積の最大化: ソート後の各行について、左から j 番目(0始まり)までを使うと「高さ temp[i][j] × 幅 (j+1)」の長方形が作れます。全行・全列でこの値を調べ、最大値を答えとして返します。

Pythonでの実装例

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

def maxArea(mat):
    row = len(mat)
    col = len(mat[0])

    # 各列について、上方向に連続する1の個数(高さ)を計算
    temp = [[0] * col for _ in range(row)]
    for j in range(col):
        temp[0][j] = mat[0][j]
        for i in range(1, row):
            if mat[i][j] == 0:
                temp[i][j] = 0
            else:
                temp[i][j] = temp[i - 1][j] + 1

    # 各行の高さを降順にソート(列の入れ替えに相当)
    for i in range(row):
        temp[i].sort(reverse=True)

    # 最大面積を求める
    area_maximum = 0
    for i in range(row):
        for j in range(col):
            area_current = (j + 1) * temp[i][j]
            if area_current > area_maximum:
                area_maximum = area_current

    return area_maximum


mat = [
    [1, 0, 0, 1, 0],
    [1, 0, 0, 1, 1],
    [1, 1, 0, 1, 0]]
print('Area :', maxArea(mat))

入力

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

出力

Area : 6

計算量

• 時間計算量: O(row × col × log col) — 各行のソート処理がボトルネックになります。
• 空間計算量: O(row × col) — 高さを格納するための一時行列が必要です。

まとめ

「列の入れ替えが許される」という条件は、各行の高さを自由にソートしてよいことと同義です。ヒストグラムの高さを前計算して降順に並べ替えるだけで、シンプルかつ効率的に1だけで構成される最大長方形の面積を求められます。全列の組み合わせを総当たりする非現実的な手法と比べ、大幅に計算量を抑えられるのがこのアルゴリズムの魅力です。