Largest Submatrix With Rearrangements LeetCode solution in Python

1
# Runtime: 3821 ms (Top 7.64%) | Memory: 37.3 MB (Top 95.14%)
2
from collections import Counter
3

4

5
class Solution:
6
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
7
        M = len(matrix)
8
        N = len(matrix[0])
9

10
        colcons = []  # preprocess columns
11
        for c in range(N):
12
            cons = []
13
            s = 0
14
            for r in range(M):
15
                if not matrix[r][c]:
16
                    s = 0
17
                else:
18
                    s += 1
19
                cons.append(s)
20
            colcons.append(cons)
21
        # colcons[c][r] is how much 1's we'll get if we start from column c at row r and go up
22

23
        best = 0
24
        for r in range(M):
25
            # try r as the lowest row
26
            C = Counter(colcons[c][r] for c in range(N))
27
            vs = sorted(C.keys(), reverse=True)
28
            cs = accumulate(C[v] for v in vs)
29
            for v, c in zip(vs, cs):
30
                best = max(best, v * c)
31
        return best