Problem statement

https://leetcode.com/problems/largest-submatrix-with-rearrangements/

Solution

The idea is for each column, find the number of consecutive ones ending at each position. Then we sort these values in non-decreasing order and look for the biggest area.

Complexity

It is O(mn log n) for time and O(n) for space.

Code

class Solution:
    def largestSubmatrix(self, A):
        def MaxArea(H):
            H, n = sorted(H), len(H)
            return max(H[i] * (n - i) for i in range(n))
        
        m, n= len(A), len(A[0])
        H, ans = [0] * n, 0
        for i in range(m):
            for j in range(n):
                H[j] = H[j] + 1 if A[i][j] else 0
            ans = max(ans, MaxArea(H))
        return ans

Remark

There is also O(mn) time complexity solution.