1727. Largest Submatrix With Rearrangements - cocoder39/coco39_LC GitHub Wiki

1727. Largest Submatrix With Rearrangements

A simple version of 85. Maximal Rectangle

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0 
        
        m, n = len(matrix), len(matrix[0])
        heights = [[0] * n for i in range(m)]
        
        for i in range(n):
            height = 0
            for j in range(m):
                if matrix[j][i] == 1:
                    height += 1
                else:
                    height = 0
                heights[j][i] = height
        
        max_area = 0
        for i in range(m):
            heights[i].sort()
            for j in range(n):
                max_area = max(max_area, (n-j) * heights[i][j])
        return max_area

T = O(M * N * logN)