Problem statement

https://binarysearch.com/problems/Largest-One-Submatrix-with-Column-Swaps/

Solution

Equal to Leetcode 1727. Largest Submatrix With Rearrangements.

Complexity

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

Code

class Solution:
    def solve(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